2019ICPC(徐州) - Who is better?(中国剩余定理+斐波那契博弈)

题目链接：点击查看

题目大意：给定k组a和b表示同余式，分别代表n%a=b，求出n后，代表有n个敌人，有两个人我们称为A和B，从A开始杀敌，第一次A可以杀至少一个敌人，至多n-1个敌人，接下来B与A轮流杀敌，每次杀敌的数目必须处于1~2k之间，k为上个人杀敌的数目。

题目分析：生硬的将中国剩余定理和斐波那契博弈结合在了一起，两个模板套起来就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; }

 

总结

以上是生活随笔为你收集整理的2019ICPC(徐州) - Who is better?(中国剩余定理+斐波那契博弈)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。