【NOIP模拟赛】蒲公英的约定

题解：
这道题如果正向做就是在线的求高阶同余方程。时间复杂度不用BSGS最坏O（nq）用了就是O（n sqrt（q））
所以就要考虑取巧的方法，因为已知第i步的答案与i-1步有关，我们又同时知道最后一步的b一定为0那么上一步的答案就为此时的c（由异或可得），那么我们就可以一步步倒退回去求得所有答案，时间复杂度O（n），秒杀此题。

#include<bits/stdc++.h>
using namespace std;
int p,n;
int lastans;
int a[100005];
int c[100005];
int ans[100005];
int read(){
	int num=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num;
}
int pow(int x,int y){
	if(y==0) return 1;
	if(y==1) return x%p;
	int k=pow(x,y>>1)%p;
	if(y&1) return (long long)k*(long long)k*(long long)x%(long long)p; 
	return (long long)k*(long long)k%(long long)p;
}
int main(){
	p=read();
	n=1;
	while(~scanf("%d%d",&a[n],&c[n])){
		n++;
	}
	n-=1;
	lastans=c[n];
	for(int i=n-1;i;i--){
		ans[i]=lastans;
		int b=pow(a[i],lastans)%p;
		lastans=b^c[i];
	}
	for(int i=1;i<=n-1;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}