A.Who is better?（The Preliminary Contest for ICPC Asia Xuzhou 2019）

https://nanti.jisuanke.com/t/41383

解：

斐波那契博弈+中国剩余定理。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 long long a[105],m[105],ans;
 4 long long exgcd(long long a,long long b,long long &x,long long &y){
 5     if (!b)
 6         {x=1,y=0;return a;}
 7     long long re=exgcd(b,a%b,x,y),tmp=x;
 8     x=y,y=tmp-(a/b)*y;
 9     return re;
10 
11 }
12 long long gcd(long long x,long long y)
13 {
14           return y==0?x:gcd(y,x%y);
15 }
16 long long work1(int n){
17           long long M=m[1];
18           for(int i=2;i<=n;i++)
19           {
20                     M=M*m[i]/gcd(M,m[i]);
21           }
22           return M;
23 }
24 
25 long long work2(int n){
26     long long M=m[1],A=a[1],t,d,x,y;
27     int i;
28     for(i=2;i<=n;i++){
29         d=exgcd(M,m[i],x,y);
30         if ((a[i]-A)%d)
31                 return -1;
32         x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;
33         A=M*x+A,M=M*m[i]/d;
34     }
35     return A;
36 }
37 long long fib[100];
38 
39 void sl(long long n)
40 {
41     int i;
42     for(i=0;i<75;i++)
43         if(fib[i]==n)
44           break;
45     if(i<75)
46           printf("Lbnb!\n");
47     else
48           printf("Zgxnb!\n");
49 }
50 int main(){
51     int k,ct=0;
52     scanf("%d",&k);
53     for(int i=1;i<=k;i++)
54     {
55               scanf("%lld%lld",m+i,a+i);
56               if(a[i]==0)
57                     ct++;
58     }
59     long long n;
60     if(ct==k)
61           n=work1(k);
62     else
63           n=work2(k);
64 
65     if(n==-1)
66           printf("Tankernb!\n");
67     else
68     {
69           fib[0]=1;fib[1]=2;
70           for(int i=2;i<75;i++)
71           {
72               fib[i]=fib[i-1]+fib[i-2];
73              // printf("%d %lld\n",i,fib[i]);
74           }
75           sl(n);
76     }
77     return 0;
78 }