链接：

题意：

给一个长为n的序列，m次操作，每次操作：

1.区间

加

2.对于区间

，查询

 

，一直到

-

请注意每次的模数不同。

 

题解：扩展欧拉定理降幂

对一个数p取log(p)次的欧拉函数等于1，故可将操作2的复杂度降到log(p)，可以直接求解。用树状数组的小技巧，可以在log的时间直接求出当前的a[i]。具体见代码。

 

#include 
      
       using namespace std;const double EPS = 1e-6;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const int maxn = 5e5 + 10;const int maxm = 2e7 + 10;int n, m;long long a[maxn], bit[maxn];int phi[maxm];void Eul_list(int n)    //欧拉函数_list{    memset(phi, 0, sizeof(phi));    phi[1] = 1;    for(int i = 2; i < n; i++){        if(!phi[i]){            for(int j = i; j < n; j += i){                if(!phi[j]) phi[j] = j;                phi[j] = phi[j] / i * (i - 1);            }        }    }}void add(int i, long long d){    while(i < maxn){        bit[i] += d;        i += -i & i;    }}long long sum(int i){    long long ans = 0;    while(i){        ans += bit[i];        i -= -i & i;    }    return ans;}long long Mod(long long x, long long y)     //欧拉定理的条件{    return x < y ? x : x % y + y;}long long pow_mod(long long x, long long n, long long mod){    long long ans = 1;    x = Mod(x, mod);    while(n){        if(n & 1) ans = Mod(ans * x, mod);        x = Mod(x * x, mod);        n >>= 1;    }    return ans;}long long dfs(int l, int r, int p){    long long val = sum(l);    if(l == r || p == 1) return Mod(val, p);    //降幂加速    return pow_mod(val, dfs(l + 1, r, phi[p]), p);}int main(){    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++){        scanf("%lld", &a[i]);        add(i, a[i] - a[i-1]);      //对i求前缀和及为a[i]    }    Eul_list(maxm);    int op, l, r, x;    while(m--){        scanf("%d%d%d%d", &op, &l, &r, &x);        if(op == 1){            //只需要当前数时的更新技巧            add(l, x);            add(r + 1, -x);        }        else printf("%lld\n", dfs(l, r, x) % x);    }    return 0;}