題目鏈接：點擊查看

題目大意：給定k組a和b表示同余式，分別代表n%a=b，求出n后，代表有n個敵人，有兩個人我們稱為A和B，從A開始殺敵，第一次A可以殺至少一個敵人，至多n-1個敵人，接下來B與A輪流殺敵，每次殺敵的數(shù)目必須處于1~2k之間，k為上個人殺敵的數(shù)目。

題目分析：生硬的將中國剩余定理和斐波那契博弈結(jié)合在了一起，兩個模板套起來就OK了，還是見識太少了

代碼：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=15;int n;LL exgcd(LL a,LL b,LL &x,LL &y) {if(!b) {//解方程求 x,y a*x+b*y = gcd(a,b)x=1,y=0;return a;}LL re=exgcd(b,a%b,x,y),tmp=x;x=y,y=tmp-(a/b)*y;return re; }LL m[N],a[N];LL work() {LL M=m[1],A=a[1],t,d,x,y;int i;for(i=2;i<=n;i++) {d=exgcd(M,m[i],x,y);//解方程if((a[i]-A)%d)return -1;//無解x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//求xA=M*x+A,M=M/d*m[i],A%=M;//日常膜一膜 防爆}A=(A%M+M)%M;return A; }LL f[75];map<LL,bool>mp;void init() {f[1]=f[2]=1;mp[1]=true;for(int i=3;i<75;i++){f[i]=f[i-1]+f[i-2];mp[f[i]]=true;} }int main() { // freopen("input.txt","r",stdin);init();while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%lld%lld",m+i,a+i);LL n=work();if(n==-1){printf("Tankernb!\n");continue;}if(mp[n])printf("Lbnb!\n");elseprintf("Zgxnb!\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的2019ICPC(徐州) - Who is better?(中国剩余定理+斐波那契博弈)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。