题目链接：http://acm.nuc.edu.cn/OJ/contest/show/54/1008
区间修改加欧拉降幂
有两种操作：
给区间[L,R]加上d输入L,R,X,输出%X的值数据范围为：
1 <= n, m <= 500000
1 <= l <= r <= n
1 <= D <= 2e9
1 <= X <= 2e7
区间欧拉降幂可以去做一下https://codeforces.com/contest/906/problem/D这个题
区间加值，单点询问显然是个树状数组啊，那么树状数组再加一个区间欧拉降幂即可了。
修改的复杂度为logn，单次查询的复杂度为logx*logn
极限数据的复杂度为m*logx*logn，那么计算次数可达：387500000次（emmm实际上应该达不到这么多吧），（学长数据出的没这么强23333）。
#include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<cstdio> using namespace std; typedef long long ll; const int maxn=2e7+9; int f[maxn]; void init(){ f[1]=1; for(int i=2;i<maxn;++i) if(f[i]==0) for(int j=i;j<maxn;j+=i){ if(!f[j]) f[j]=j; f[j]=f[j]/i*(i-1); } } ll sum[500007]; int a[500007]; int lowbit(int x){ return x&(-x); } int n; void add(int x,int y){ for(;x<=n;x+=lowbit(x)) sum[x]+=y; } ll ask(int x){ ll res=0; for(;x;x-=lowbit(x)) res+=sum[x]; return res; } ll MOD(ll a,ll b){ return a>=b?a%b+b:a; } ll quick(ll a,ll b,ll mod){ ll res=1; while(b){ if(b&1) res=MOD(res*a,mod); a=MOD(a*a,mod); b>>=1; } return res; } ll jisuan(int l,int r,int mod){ ll x=ask(l); if(l==r||mod==1) return MOD(x,mod); return quick(x,jisuan(l+1,r,f[mod]),mod); } template <class T> inline void scan_d(T &ret) { char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'), c = getchar(); } } int main(){ int m; init(); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //scanf("%d%d",&n,&m); scan_d(n),scan_d(m); for(int i=1;i<=n;++i){ //scanf("%d",&a[i]); scan_d(a[i]); //sum[i]=a[i]-a[i-1]; add(i,a[i]-a[i-1]); } int id,x,y,z; while(m--){ //scanf("%d%d%d%d",&id,&x,&y,&z); scan_d(id),scan_d(x),scan_d(y),scan_d(z); if(id==1){ add(x,z); add(y+1,-z); } else{ printf("%lld\n",jisuan(x,y,z)%z); } } return 0; } //int main(){ // freopen("in.txt","w",stdout); // int n=500000,m=500000; // printf("%d %d\n",n,m); // printf("%d",1); // for(int i=2;i<=n;++i) // printf(" %d",i); // printf("\n"); // for(int i=1;i<=m;++i) // printf("2 1 500000 20000000\n"); // //}
