# 2019 Xuzhou network A (Chinese remainder theorem is non coprime m+ for Fibonacci number).

Topic link https://nanti.jisuanke.com/t/41383 Who is better?
The topic is divided into two parts. First, find out the smallest n, and then decide who wins by game.
Finding the process of n is a variant of the Chinese remainder theorem, without giving the condition of m coprime, proving the process https://www.iteye.com/blog/yzmduncan-1323599.
Board:

```void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) {
d = a, x = 1, y = 0;
}
else {
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
LL crt(LL *m, LL *r, int n) {
LL M = m, R = r, x, y, d;
for (int i = 2; i <= n; ++i) {
gcd(M, m[i], d, x, y);
if ((r[i] - R) % d)
return -1;
x = (r[i] - R) / d * x % (m[i] / d);
R += x * M;
M = M / d * m[i];
R %= M;
}
return R > 0 ? R : R + M;
}
```

Return - 1 if nonexistent
If n is Fibonacci number, the back wins, otherwise the front wins, which can be proved by mathematical induction.
Fibonacci judged the cycle of violence, because it had already exceeded ll 100 times.

```#include <bits/stdc++.h>
#define N 1025
#define LL long long
const LL mod=1000000007;
const double pi = acos(-1.0);
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
int n;
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) {
d = a, x = 1, y = 0;
}
else {
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
LL crt(LL *m, LL *r, int n) {
LL M = m, R = r, x, y, d;
for (int i = 2; i <= n; ++i) {
gcd(M, m[i], d, x, y);
if ((r[i] - R) % d)
return -1;
x = (r[i] - R) / d * x % (m[i] / d);
R += x * M;
M = M / d * m[i];
R %= M;
}
return R > 0 ? R : R + M;
}
LL m[maxn], r[maxn];
int main() {

cin >> n;
for (int i = 1; i <= n; ++i)
cin>>m[i]>>r[i];
LL x = crt(m, r, n),y=1;
if (x > 1e15||x<=0)
cout << "Tankernb!";
else
{
for (LL i = 1, j = 1; i <= 1e15;)
{
y = i + j;
j = i;
i = y;
if (y >= x)
break;
}
if (y == x)
cout << "Lbnb!";
else cout << "Zgxnb!";
}
//system("pause");
return 0;
}
```

Added by davidb on Tue, 08 Oct 2019 10:59:28 +0300