记录编号	440415	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[thusc2015]平方运算	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.173 s
提交时间	2017-08-23 08:43:51	内存使用	13.28 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=4e5+10;
int n,m,p,a[N],tp,l,r;
void vio(){
	while (m--){
		scanf("%d%d%d",&tp,&l,&r);
		if (tp==0)
			for (int i=l;i<=r;i++) a[i]=a[i]*a[i]%p;
		else{
			int ans=0;
			for (int i=l;i<=r;i++) ans+=a[i];
			printf("%d\n",ans);
		}
	}
}
int go[N],vis[N],len=1,num;
bool incir[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void init(){
	for (int i=0;i<p;i++) go[i]=i*i%p;
	for (int i=0;i<p;i++)
	if (!vis[i]){
		int x=i;
		for (x=i;!vis[x];x=go[x]) vis[x]=i+1;
		if (vis[x]!=i+1) continue;
		num++;
		int cnt=1,end=x;
		incir[x]=1;
		for (x=go[x];x!=end;x=go[x]) incir[x]=1,cnt++;
		len=len/gcd(len,cnt)*cnt;
	}
}
struct segment_tree{
	int id,now[N],tag[N];
	vector<int> list[N];
	bool not_in_cir[N];
	#define lc x<<1
	#define rc x<<1|1
	void move(int &x,int p){
		x+=p;
		if (x>=len) x-=len;
	}
	void update(int x){
		int p=now[x],pl=now[lc],pr=now[rc];
		for (int i=0;i<len;i++){
			list[x][p]=list[lc][pl]+list[rc][pr];
			move(p,1);move(pl,1);move(pr,1);
		}
		not_in_cir[x]=not_in_cir[lc]||not_in_cir[rc];
	}
	void add(int x,int p){
		move(now[x],p);
		move(tag[x],p);
	}
	void pushdown(int x){
		if (tag[x]){
			add(lc,tag[x]);
			add(rc,tag[x]);
			tag[x]=0;
		}
	}
	void newnode(int x,int val){
		not_in_cir[x]=!incir[val];
		for (int i=0;i<len;i++) list[x][i]=val,val=go[val];
	}
	void init(int x,int l,int r){
		now[x]=0;
		list[x].resize(len,0);
		if (l==r) return newnode(x,a[l]);
		int mid=(l+r)>>1;
		init(lc,l,mid);
		init(rc,mid+1,r);
		update(x);
	}
	void move(int x,int l,int r,int L,int R){
		if (l>=L&&r<=R&&!not_in_cir[x]) return add(x,1);
		if (l==r) return newnode(x,go[list[x][now[x]]]);
		pushdown(x);
		int mid=(l+r)>>1;
		if (L<=mid) move(lc,l,mid,L,R);
		if (R>mid) move(rc,mid+1,r,L,R);
		update(x);
	}
	int query(int x,int l,int r,int L,int R){
		if (l>=L&&r<=R) return list[x][now[x]];
		pushdown(x);
		int mid=(l+r)>>1,ans=0;
		if (L<=mid) ans+=query(lc,l,mid,L,R);
		if (R>mid) ans+=query(rc,mid+1,r,L,R);
		return ans;
	}
}T;
int main()
{
	freopen("thusc2015_square.in","r",stdin);
	freopen("thusc2015_square.out","w",stdout);
	scanf("%d%d%d",&n,&m,&p);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	//if (n*m<=1e8) vio();
	init();
	T.init(1,1,n);
	while (m--){
		scanf("%d%d%d",&tp,&l,&r);
		if (tp==0) T.move(1,1,n,l,r);else printf("%d\n",T.query(1,1,n,l,r));
	}
	return 0;
}