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[1], R = r[1], 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[1], R = r[1], 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; }