BZOJ4869 [Shoi2017]相逢是问候【扩展欧拉定理 + 线段树】

题目链接

题解

这题调得我怀疑人生，，结果就是因为某些地方\(sb\)地忘了取模

前置题目：BZOJ3884

扩展欧拉定理：

\[c^a \equiv c^{a \mod \varphi(p) + [a \ge p]p} \pmod p
\]

我们发现当我们进行\(0\)操作，就相当于在\(a\)底部添加一层\(c\)

当我们进行得足够多的时候，\(\varphi(p)\)就会取到\(1\)，从而不再变化

所以每个位置操作次数其实是有限的，为\(O(logp)\)次

为何是\(O(logp)\)次呢？

考虑欧拉函数：

\[\varphi(n) = n \prod\limits_{i = 1}^{k} \frac{p_i - 1}{p_i}
\]

由于质数一定是奇数，所以\(p_i - 1\)一定为偶数，所以操作一次后的\(p\)一定为偶数

偶数有\(2\)这个质因子，式子中就会存在\(\frac{1}{2}\)这一项，所以至少减少\(\frac{1}{2}\)

所以到达\(1\)是\(O(logp)\)的

用线段树进行维护

每次修改重新计算\(O(log^2p)\)，总复杂度\(O(nlognlog^3p)\)，凭信仰可过

由于每次快速幂底都是\(c\)，我们可以预处理\(c^x\)，从而做到\(O(nlognlog^2p)\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define ls (u << 1)

#define rs (u << 1 | 1)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

inline int read(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

    return out * flag;

}

int p[maxn],pi,isn[maxn];

void init(){

    for (int i = 2; i <= 10000; i++){

        if (!isn[i]) p[++pi] = i;

        for (int j = 1; j <= pi && i * p[j] <= 10000; j++){

            isn[i * p[j]] = true;

            if (i % p[j] == 0) break;

        }

    }

}

int n,m,P[30],Pi,c,a[maxn],cnt[maxn],low[30];

LL C[30][maxn],CC[30][maxn];

int phi(int x){

    int tmp = x,ans = x;

    for (int i = 1; i <= pi && p[i] <= tmp; i++){

        int v = p[i];

        if (tmp % v == 0){

            ans = ans / v * (v - 1);

            while (tmp % v == 0) tmp /= v;

        }

    }

    if (tmp - 1) ans = ans / tmp * (tmp - 1);

    return ans;

}

LL qpow(int b,int md){

    return CC[md][b / 10000] * C[md][b % 10000] % P[md];

}

int cal(int x,int t){

	LL last,tmp = x;

    if (tmp > P[t]) tmp = tmp % P[t] + P[t];

    for(int i = t; i; i--)

    {

        last = tmp;

        tmp = qpow(tmp,i - 1);

        if (last >= low[i - 1]){

			tmp += P[i - 1];

		}

    }

    return tmp;

}

int sum[maxn << 2],val[maxn << 2];

void upd(int u){

    sum[u] = (sum[ls] + sum[rs]) % P[0];

    val[u] = val[ls] | val[rs];

}

void build(int u,int l,int r){

    val[u] = 1;

    if (l == r){sum[u] = a[l] % P[0]; return;}

    int mid = l + r >> 1;

    build(ls,l,mid);

    build(rs,mid + 1,r);

    upd(u);

}

void change(int u,int l,int r){

    if (!val[u]) return;

    if (l == r){

        cnt[l]++;

        if (cnt[l] >= Pi) val[u] = 0;

        sum[u] = cal(a[l],cnt[l]) % P[0];

        return;

    }

    int mid = l + r >> 1;

    change(ls,l,mid);

    change(rs,mid + 1,r);

    upd(u);

}

void modify(int u,int l,int r,int L,int R){

    if (!val[u]) return;

    if (l >= L && r <= R){

        change(u,l,r);

        return;

    }

    int mid = l + r >> 1;

    if (mid >= L) modify(ls,l,mid,L,R);

    if (mid < R) modify(rs,mid + 1,r,L,R);

    upd(u);

}

int query(int u,int l,int r,int L,int R){

    if (l >= L && r <= R) return sum[u] % P[0];

    int mid = l + r >> 1;

    if (mid >= R) return query(ls,l,mid,L,R);

    if (mid < L) return query(rs,mid + 1,r,L,R);

    return (query(ls,l,mid,L,R) + query(rs,mid + 1,r,L,R)) % P[0];

}

int main(){

    init();

    n = read(); m = read(); P[0] = read(); c = read();

    REP(i,n) a[i] = read();

    while (P[Pi] != 1){

        ++Pi;

        P[Pi] = phi(P[Pi - 1]);

    }

	P[++Pi] = 1;

    for (register int t = 0; t <= Pi; t++){

        C[t][0] = CC[t][0] = 1 % P[t];

		low[t] = 0;

        for (register int i = 1; i <= 10000; i++){

			C[t][i] = C[t][i - 1] * c;

			if (C[t][i] >= P[t] && !low[t]) low[t] = i;

			C[t][i] %= P[t];

		}

		CC[t][1] = C[t][10000];

		for (register int i = 2; i <= 10000; i++)

			CC[t][i] = CC[t][i - 1] * C[t][10000] % P[t];

    }

    build(1,1,n);

    int opt,l,r;

    while (m--){

        opt = read(); l = read(); r = read();

        if (!opt) modify(1,1,n,l,r);

        else printf("%d\n",query(1,1,n,l,r));

    }

    return 0;

}

巴特西

BZOJ4869 [Shoi2017]相逢是问候【扩展欧拉定理 + 线段树】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ4869 [Shoi2017]相逢是问候 【扩展欧拉定理 + 线段树】

题目链接

题解

最新文章

热门文章

BZOJ4869 [Shoi2017]相逢是问候【扩展欧拉定理 + 线段树】