本文主要是介绍BZOJ 4869 [Shoi2017]相逢是问候 扩展欧拉定理+线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Informatikverbindetdichundmich.
信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以
分为两种：0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是
输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为
这个结果可能会很大，所以你只需要输出结果mod p的值即可。
Input
第一行有三个整数n,m,p,c，所有整数含义见问题描述。
接下来一行n个整数，表示a数组的初始值。
接下来m行，每行三个整数，其中第一个整数表示了操作的类型。
如果是0的话，表示这是一个修改操作，操作的参数为l,r。
如果是1的话，表示这是一个询问操作，操作的参数为l,r。
1 ≤ n ≤ 50000, 1 ≤ m ≤ 50000, 1 ≤ p ≤ 100000000, 0 < c <p, 0 ≤ ai < p
Output
对于每个询问操作，输出一行，包括一个整数表示答案mod p的值。
Sample Input
4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3
Sample Output
0
3
3
HINT
鸣谢多名网友提供正确数据，已重测！
传送门
直接做似乎有点不可做，，
虽然知道扩展欧拉定理但是还是不会= =
一个感觉当然是假如x操作后，c^x=x，那么显然x就没有必要再去更改了。
但是……这个是若干次操作后一定存在的吗？
存在的话是最多几次呢？
……答案是肯定的。
假设一个x，那么一次操作变成c^x，两次变成c^(c^x)
根据扩展欧拉定理，假设x>phi（p），
c^x=c^(x%phi(p)+phi(p))
令其为t，
两次的话，变成了c^t，
再次利用定理的话，其实就是
c^t=c^(t%phi(p)+phi(p)) (mod p)
观察一下：t%phi(p)其实就是c的若干次方%phi(p)，所以t可以满足：
t=c^x=c^[c^(x%phi(phi(p))+phi(phi(p)))%phi(p)+phi(p)] (mod p)
……形成了一个递归结构。。
（不太会用markdown，，式子就很丑了QAQ）
然后对于一个p，p->phi(p)->phi(phi(p))->……->1，
这个过程有多长呢？对于一个偶数，求一次phi就会减小一半大小，
而对于奇数，假如是质数就会变成偶数，而假如不是质数其实也是一样的，
根据欧拉函数公式，某一个奇数因子减1之后一定会变成偶数的，
所以奇数求欧拉函数会变成偶数。
所以这个过程最长长度是log(p)
知道了这个结论的话。。对于c^(c^(c^……
对于求幂次的次数，简称为“层数”
那么就是说最上面的一层x%phi(p)+phi(p)，这个phi(p)=1
于是x%phi(p)+phi(p)=1，对于任意的x，
那么层数再多下去，上面再多叠几层，都是没有影响的了，
真正有效的层数始终只有O(log(p))，
所以暴力的时间复杂度就被保证了。
接下来用一个线段树维护即可。
线段树一个log……求层数一个log……每次快速幂还要一个log……
于是就3个log了……幸好bzoj 40s。。
但是洛谷就被光荣卡常TLE了。。。
听说有一种去掉快速幂log的方法。。不是很懂所以就没去管了。。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){int x=0;char ch=getchar();while (ch<'0'||ch>'9')ch=getchar();while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x;
}
const int N=50005;
int n,m,P,c,len,DEEPEST;
int a[N],dep[N],depphi[50],prime[1305];
bool notprime[10005];
struct Segment{int sum;bool flag;}seg[N<<2];
void up(int id){seg[id].sum=(seg[id<<1].sum+seg[id<<1|1].sum)%P;seg[id].flag=seg[id<<1].flag&seg[id<<1|1].flag;
}
int gcd(int a,int b){return (!b)?a:gcd(b,a%b);
}
void Pre_Prime(){notprime[1]=1;for (int i=2;i<=9974;i++){if (!notprime[i]) prime[++len]=i;for (int j=1;j<=len;j++){if (prime[j]*i<=9974) notprime[prime[j]*i]=1;if (i%prime[j]==0) break;}}
}
int phi(int x){ll t1=(ll)x;int p=1;while (p<=len && x>1){if (x%prime[p]==0){t1/=(ll)prime[p];t1*=(ll)prime[p]-1;while (x%prime[p]==0) x/=prime[p];}p++;}if (x!=1) t1*=(ll)x-1,t1/=(ll)x;return t1;
}
void Pre_Phi(int p){int t=phi(p);depphi[DEEPEST=0]=p;while (t!=p){depphi[++DEEPEST]=t;p=t,t=phi(p);}depphi[DEEPEST+1]=1;
/* cout<<DEEPEST<<endl;for (int i=1;i<=DEEPEST;i++)cout<<depphi[i]<<' ';cout<<endl;*/
}
int ksm(int x,int y,int mod){int z=1,xx=x;while (y){if (y&1) z=(ll)z*xx%mod;y>>=1;xx=(ll)xx*xx%mod;}return z;
}
int calc(int d,int x){int t=x;if (t>depphi[d]) t=t%depphi[d]+depphi[d];while (d--){t=ksm(c,t,depphi[d]);if (gcd(c,t)!=1) t+=depphi[d];}return t%P;
}
void build(int id,int l,int r){if (l==r){seg[id].sum=a[l],seg[id].flag=0;return;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);up(id);
}
void update(int id,int l,int r,int gl,int gr){if (l==r){if (dep[l]>DEEPEST) return;seg[id].sum=calc(++dep[l],a[l]);if (dep[l]>DEEPEST) seg[id].flag=1;return;}int mid=(l+r)>>1;if (gl<=mid && !seg[id<<1].flag) update(id<<1,l,mid,gl,gr);if (gr>mid && !seg[id<<1|1].flag) update(id<<1|1,mid+1,r,gl,gr);up(id);
}
int query(int id,int l,int r,int gl,int gr){if (l>=gl && r<=gr) return seg[id].sum;int mid=(l+r)>>1,t=0;if (gl<=mid) t=((ll)t+query(id<<1,l,mid,gl,gr))%P;if (gr>mid) t=((ll)t+query(id<<1|1,mid+1,r,gl,gr))%P;return t;
}
int main(){Pre_Prime();n=read(),m=read(),P=read(),c=read();Pre_Phi(P);for (int i=1;i<=n;i++) a[i]=read();build(1,1,n);int opt,l,r;while (m--){opt=read(),l=read(),r=read();if (!opt) update(1,1,n,l,r);else printf("%d\n",query(1,1,n,l,r));} return 0;
}这篇关于BZOJ 4869 [Shoi2017]相逢是问候 扩展欧拉定理+线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
