蒲公英的约定

题解：

考试时以为是一道高次同余方程题，然后只打了一个暴力。

最后DB发现只需要通过输入中的最后一行倒推回去就行了。首先根据题目我们知道，输入中的最后一行中b等于0。那么就是        c ^ LastAns = 0。根据异或的性质我们知道c = LastAns。于是最后一个答案一定是c。

那么就可以知道倒数第二行中的x = c，即中只有b不知道了。又由题目可以得出，于是b求得，观察  c ^ LastAns = b由性质得 c ^ b = LastAns，于是又求出了倒数第二个答案。以此类推，可以从下往上依次求出所有答案，最后再逆序输出即可。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAXA 100500
using namespace std;
typedef long long LL;
int MOD;
LL FastPow(LL a,LL b) {LL Ans = 1;while(b) {if(b & 1)Ans = Ans * a % MOD;a = a * a % MOD;b >>= 1;}return Ans;
}
vector Ans;
int a[MAXA],c[MAXA],cnt = 1,LastX,b;
int main() {scanf("%d",&MOD);while(cin >> a[cnt] >> c[cnt]) {cnt++;}cnt--;Ans.push_back(c[cnt]);LastX = c[cnt];for(int i=cnt-1;i>=2;i--) {b = FastPow(a[i],LastX) % MOD;LastX = c[i] ^ b;Ans.push_back(LastX);}for(int i=Ans.size()-1;i>=0;i--)printf("%d\n",Ans[i]);
}
/*
17
2 8
8 11
5 5
4 12
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！