提交记录

rt，样例能过，感觉像是 get_ans 函数的问题，但是就是看不出来/kel

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+1;
const int V=2e7+1;
int cnt,prime[V];
int n,m,phi[V];
bool st[V];

int read() {
	int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
	while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return x;
}
struct BIT
{
	int T[N];
	void add(int x,int y) { while (x<=n) T[x]+=y,x+=x&-x; }
	int query(int x,int sum=0) { while (x) sum+=T[x],x-=x&-x; return sum; }
	void change(int x,int y,int z) { add(x,z),add(y+1,-z); }
}A;

void get_primes(int n)
{
	phi[1]=1;
	memset(st,1,sizeof st);
	for (int i=2;i<=n;i++)
	{
		if (st[i]) prime[++cnt]=i,phi[i]=i-1;
		for (int j=1;prime[j]<=n/i;j++)
		{
			st[i*prime[j] ]=false;
			if (i%prime[j]==0) { phi[i*prime[j] ]=phi[i]*prime[j]; break; }
			else phi[i*prime[j] ]=phi[i]*(prime[j]-1);
		}
	}
}
int power(int a,int b,int p)
{
	int ans=1%p; while (b) {
		if (b&1) ans=ans*a%p;
		a=a*a%p,b>>=1;
	}return ans;
}
int get_ans(int l,int r,int p)
{
	int now=A.query(l),ans; if (l==r||p==1) ans=now;
	else ans=power(now,get_ans(l+1,r,phi[p]),p);
	return ans>=p?ans%p+p:ans;
}
signed main()
{
	get_primes(V-1); n=read(),m=read();
	for (int i=1;i<=n;i++) A.change(i,i,read() );
	while (m--) { int op=read(),l=read(),r=read(),x=read();
	if (op==1) A.change(l,r,x); else printf("%d\n",get_ans(l,r,x)%x); }
	return 0;
}