这是之前写的 calc 函数

inline int calc(int l,int r,int p){
	if(bit::q(l)==1)return 1;
	if(p==1){
		flag[l]=1;
		return 0;
	}
	if(l==r){
		int ret = bit::q(l);
		if(ret >= p)flag[l] = 1;
		return ret%p;
	}
	int ans = calc(l+1,r,phi[p]);
	if(flag[l+1])ans+=phi[p];
	int ret=bit::q(l);
	auto pt=bfpow(ret,ans,p);
	flag[l]|=pt.second;
	return pt.first;
}

这是之后写的

inline pair<int,bool> calc(int l,int r,int p){
	int ret=bit::q(l);
	if(p==1)return {0,1};
	if(ret==1)return {1,0};
	if(l==r) return ret<p?make_pair(ret,0):make_pair(ret%p,1);
	int ph=phi[p];
	auto ans = calc(l+1,r,phi[p]);
	if(ans.second)ans.first+=ph;
	return bfpow(ret,ans.first,p);
}

为什么上面的WA on 10而下面的能AC

附全代码：

#include <bits/stdc++.h>

using namespace std;

namespace IO {
    template <typename T> inline void fr(T &num) {
        num = 0;
        short sign = 1;
        char ch = std::getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                sign = -1;
            ch = std::getchar();
        }
        while (ch >= '0' && ch <= '9')
            num = num * 10 + ch - '0', ch = getchar();
        num = num * sign;
    }
    template <> inline void fr(char &ch) {
        ch = std::getchar();
        while (ch < 'A' || ch > 'z' || (ch > 'Z' && ch < 'a'))
            ch = std::getchar();
    }
    template <> inline void fr(string &s) {
        s = "";
        char ch = std::getchar();
        while (ch != ' ' || ch != '\n')
            s += ch, ch = std::getchar();
    }
    template <typename T, typename... Args>
    inline void fr(T &num, Args &...args) {
        fr(num), fr(args...);
    }
    template <typename T> inline void fw(T x) {
        if (x < 0)
            std::putchar('-'), x = -x;
        if (x > 9)
            fw(x / 10);
        std::putchar(x % 10 + '0');
    }
    template <> inline void fw(char ch) { putchar(ch); }
    template <> inline void fw(string ch) {
        for (auto c : ch)
            fw(c);
    }
    char _sep = ' ', _end = '\n';
    template <typename T, typename... Args>
    inline void fw(T num, Args... args) {
        fw(num), fw(_sep), fw(args...), fw(_end);
    }
} // namespace IO

const int M=2e7+5,N=1e6+5;
#define int __int128

namespace bit{
	int val[N], n;
	inline int lb(int x){return x&-x;}
	inline void c(int p,int x){while(p<=n)val[p]+=x,p+=lb(p);}
	inline int q(int p){if(!p)return 0;int ret = 0;while(p)ret+=val[p],p-=lb(p);return ret;}
}

bool flag[N];
inline pair<int,bool> bfpow(int a,int b,const int p){
	int ans=1;
	bool rrt=false;
	if(a>=p)rrt=true,a%=p;
	while(1){
		if(b&1){
			ans*=a;
			if(ans>=p)rrt=true,ans%=p;
		}
		b >>= 1;
		if(!b)break;
		a = (__int128_t)a*a;
		if(a>=p)rrt=true,a%=p; 
	}
	return make_pair(ans, rrt);
}

int phi[M];
bool vis[M];
vector<int> prime;
inline void init(){
	phi[1] = 1;
	for(int i=2;i<M;++i){
		if(!vis[i])phi[i]=i-1,prime.emplace_back(i);
		for(auto p:prime){
			if(p*i>=M)break;
			vis[p*i] = 1;
			if(i%p == 0){
				phi[i*p] = phi[i]*p;
				break;
			}
			phi[i*p] = phi[i]*phi[p];
		}
	}
}

//inline int calc(int l,int r,int p){
//	if(bit::q(l)==1)return 1;
//	if(p==1){
//		flag[l]=1;
//		return 0;
//	}
//	if(l==r){
//		int ret = bit::q(l);
//		if(ret >= p)flag[l] = 1;
//		return ret%p;
//	}
//	int ans = calc(l+1,r,phi[p]);
//	if(flag[l+1])ans+=phi[p];
//	int ret=bit::q(l);
//	auto pt=bfpow(ret,ans,p);
//	flag[l]|=pt.second;
//	return pt.first;
//}
inline pair<int,bool> calc(int l,int r,int p){
	int ret=bit::q(l);
	if(p==1)return {0,1};
	if(ret==1)return {1,0};
	if(l==r) return ret<p?make_pair(ret,0):make_pair(ret%p,1);
	int ph=phi[p];
	auto ans = calc(l+1,r,phi[p]);
	if(ans.second)ans.first+=ph;
	return bfpow(ret,ans.first,p);
}
signed main(){
	using IO::fr;
	using IO::fw;
	//freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
	init();
	int n,m;
	fr(n,m);
	bit::n = n+1;
	for(int i=1;i<=n;++i){
		int x;
		fr(x);
		bit::c(i,x),bit::c(i+1,-x);
	}
//	cout << 111 << endl;
	while(m--){
		int op,l,r,x;
		fr(op,l,r,x);
		if(op == 1){
			bit::c(l,x),bit::c(r+1,-x);
		}
		else{
			fw(calc(l,r,x).first),putchar('\n');
		}
	}
	return 0;
}

/*
3 1
2 2 1
2 1 3 8
*/