传送门

A. Who is better?

扩展中国剩余定理+斐波那契博弈，没啥好说的，关于斐波那契博弈，详见：传送门

Code

```cpp #include using namespace std; typedef long long ll; const int N = 15; const ll MAX = 1e15; int k; ll a[N], b[N]; void exgcd(ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1, y = 0; return ; } exgcd(b, a % b, x, y); int t = x; x = y; y = t - (a / b) * y; } ll fib[100]; map mp; void pre() { fib[1] = fib[2] = 1; for(int i = 3; ;i++) { fib[i] = fib[i - 2] + fib[i - 1]; if(fib[i] > MAX) break; mp[fib[i]] = 1; } mp[1] = 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); pre(); cin >> k; for(int i = 1; i <= k; i++) { cin >> a[i] >> b[i]; } ll n = b[1], m = a[1]; for(int i = 2; i <= k; i++) { ll g = __gcd(m, a[i]); ll tmp = ((b[i] - n) % a[i] + a[i]) % a[i]; if(tmp % g != 0) { cout << "Tankernb!"; return 0; } ll x, y; exgcd(m / g, a[i] / g, x, y); x = x * (tmp / g); x = (x % a[i] + a[i]) % a[i]; n += x * m; m = m / g * a[i]; n %= m; if(n > MAX) { cout << "Tankernb!"; return 0; } } if(mp[n]) cout << "Lbnb!"; else cout << "Zgxnb!"; return 0; } ``` ,>

B. so easy

并查集+\(map\)就行，还可以离散化搞一下，把\(i+1\)顺便离散化一下就行。

Code

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int MAXN = 1e6+5,MAXM = 1e6+5,MOD = 1e9+7,INF = 0x3f3f3f3f,N=100050;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const db eps = 1e-9;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define mid l + ((r-l)>>1)
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define vii vector<pair<int,int>>
#define vi vector<int>
using namespace std;
int n,q,X[MAXN<<1],len,fa[MAXN<<1],v[MAXN],v2[MAXN],mp[MAXN<<1];
struct Ques{
    int z,x;
}Q[MAXM];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
struct Istream {
    template <class T>
    Istream &operator >>(T &x) {
        static char ch;static bool neg;
        for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
        for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
        x=neg?-x:x;
        return *this;
    }
}fin;
int main(){
    //ios::sync_with_stdio(false);cin.tie(0);
    //freopen("../A.in","r",stdin);
    //freopen("../A.out","w",stdout);
    fin>>n>>q;
    for(register int i=1;i<=q;i++){
        fin>>Q[i].z>>Q[i].x;
        X[++len]=Q[i].x;
        X[++len]=Q[i].x+1;
    }
    sort(X+1,X+1+len);
    len=unique(X+1,X+1+len)-X-1;
    for(int i=1;i<=len;i++)fa[i]=i;
    for(int i=1;i<=q;i++){
        v[i] = lower_bound(X+1,X+1+len,Q[i].x)-X;
        v2[i] = lower_bound(X+1,X+1+len,Q[i].x+1)-X;
        mp[v[i]] = Q[i].x;
        mp[v2[i]] = Q[i].x+1;
    }
    int ans=0;
    for(int i=1;i<=q;i++){
        if(Q[i].z==1){
            if(fa[v[i]]==v[i])fa[v[i]] = find(v2[i]);
        }else{
            ans=mp[find(v[i])];
            if(ans==n+1)printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}