D. Two chandeliers CRT + 二分

D. Two chandeliers CRT + 二分

题目大意：

给你两个序列，一个长度为 n，一个长度为 m，这两个序列的数都是两两互不相同的，这两个序列都是可以无限循环的，这两个序列里面的值都是小于等于 (2*max(n,m)) ，问当这两个序列长度为多少是，最少有 (k) 个位置的数是不同的。

题解：

很容易想到可以进行二分，二分答案，然后遍历 (2*max(n,m)) 求每一个数有多少个位置是相同的，这个可以用中国剩余定理(CRT)求解：

[pos = x (mod \,n) ]

[pos = y(mod\,m) ]

求出有多少个一样的之后，然后判断此时的长度是否合适即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0){x=1;y=0;return a;}
    long long gcd=exgcd(b,a%b,x,y);
    long long tp=x;
    x=y; y=tp-a/b*y;
    return gcd;
}
int ai[10],bi[10];
long long mul(long long a,long long b,long long mod)
{
    long long res=0;
    while(b>0){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
long long excrt()
{
    long long x,y;
    long long M=bi[1],ans=ai[1];
    long long a=M,b=bi[2],c=(ai[2]-ans%b+b)%b;
    long long gcd=exgcd(a,b,x,y),bg=b/gcd;
    if(c%gcd!=0) return -1;
    x=mul(x,c/gcd,bg);
    ans+=x*M,M*=bg;
    ans=(ans%M+M)%M;
    return ans;
}
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll n,m,k,LCM,crt[maxn];
int a[maxn],b[maxn];
bool check(ll x){
    ll ans = 0;
    int len = 2*max(n,m);
    for(int i=1;i<=len;i++) {
        if (a[i] && b[i] && a[i] <= x && b[i] <= x) {
            ll v = crt[i];
            if (v != -1 && x >= v) {
                ans += (x - v) / LCM;
                if (v > 0) ans++;
            }
        }
        if(x-ans<k) return false;
    }
    return x - ans >= k;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    LCM = lcm(n,m);
    for(int i=1,x;i<=n;i++) scanf("%d",&x),a[x] = i;
    for(int i=1,x;i<=m;i++) scanf("%d",&x),b[x] = i;
    int len = 2*max(n,m);
    for(int i=1;i<=len;i++){
        if(a[i]&&b[i]){
            bi[1] = n, bi[2] = m;
            ai[1] = a[i] % n, ai[2] = b[i] % m;
            crt[i] = excrt();
        }
    }
    ll l = 1,r = 2*max(n,m)*k,ans = 0;
    while(l<=r){
        ll mid = (l+r)>>1;
        if(check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    printf("%lld
",ans);
    return 0;
}