题目链接
题意：
给定一个长度为nnn的序列，进行mmm次操作，操作有两类：
111 LLL RRR vvv ： 区间[L,R][L, R][L,R]的每个数加上vvv
222 LLL RRR ppp ： 查询a[L]a[L+1]a[L+2]...a[R]modpa[L] ^ {a[L+1] ^ {a[L + 2] ^{...^{a[R]}}}} \ mod \ pa[L]a[L+1]a[L+2]...a[R]modp
思路：
利用拓展欧几里德定理：
axmodp=axmodφ(p)+(x>φ(p)?φ(p):0)modpa^x \ mod \ p = a ^{x \ mod \ \varphi(p) + (x > \varphi(p)?\varphi(p):0 ) } \ mod \ paxmodp=axmodφ(p)+(x>φ(p)?φ(p):0)modp
因为一个数ppp只需要在logplog plogp次取欧拉函数以后就会变成1，而任何数mod1mod 1mod1都是0，故实际上只需要计算前logplog plogp个数带入表达式的值，利用递归即可求解。
代码：
#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<cstdio>using namespace std;typedef long long ll;const int A = 1e6 + 10;const int B = 2e7 + 10;ll Tree[A];int pri[B], phi[B], tot, n, m;bool vis[B];void Init(){tot = 0;phi[1] = 1;for (int i = 2; i < B; i++) {if (!vis[i]) {pri[++tot] = i; phi[i] = i-1;}for (int j = 1; j <= tot && i * pri[j] < B; j++) {vis[i * pri[j]] = 1;if (i % pri[j] == 0) {phi[i * pri[j]] = pri[j] * phi[i];break;}phi[i * pri[j]] = phi[pri[j]] * phi[i];}}}ll calc(ll x, ll mod){return x > mod?x%mod+mod:x;}void update(int x, int v){for (int i = x; i <= n; i += (i & (-i))) Tree[i] += v;}ll get_sum(int x) {ll res = 0;for (int i = x; i > 0; i -= (i & (-i))) {res += Tree[i];}return res;}ll fast_mod(ll n, ll m, int mod){ll res = 1;n = calc(n, mod);while(m > 0){if (m & 1) res = calc(res * n, mod);n = calc(n*n, mod);m >>= 1;}return res;}ll dfs(int l, int r, int mod){if (l == r || mod == 1) return calc(get_sum(l), mod);return fast_mod(get_sum(l), dfs(l + 1, r, phi[mod]), mod);}int main(){Init();scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {int x;scanf("%d", &x);update(i,x);update(i+1,-x);}for (int i = 1; i <= m; i++) {int op, l, r, v;scanf("%d%d%d%d", &op, &l, &r, &v);if(op == 1){update(l,v);update(r + 1, -v);} else {printf("%lld\n", dfs(l, r, v) % v);}}return 0;}
如果觉得《牛客练习赛22 E 树状数组 + DFS + 拓展欧几里德定理》对你有帮助，请点赞、收藏，并留下你的观点哦！
