【luogu P3868】 [TJOI2009]猜数字

 https://www.luogu.org/problemnew/show/P3868

  这是一道中国剩余定理的板子题，所以直接写就好了(划死），好吧这道题良（du）心（liu）的出题人让这道题必须用快速乘（因为会爆long long）

 要切记使得所有a[i] = (a[i] % b[i] + b[i]) % b[i];

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
typedef long long ll;
using namespace std;
const int maxn = 20;
int k;
ll a[maxn], b[maxn];
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 mul(ll a, ll b, ll mod) {
    ll ans = 0;
    while(b > 0) {
        if(b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}
ll china() {
    ll ans = 0, lcm = 1, x, y;
    for(int i = 1; i <= k; i++)
        lcm *= b[i];
    for(int i = 1; i <= k; i++) {
        ll t = lcm / b[i];
        exgcd(t,b[i],x,y);
        x = (x % b[i] + b[i]) % b[i];
        ans = (ans + mul(mul(t,x,lcm),a[i],lcm)) % lcm;
    }
    return (ans + lcm) % lcm;
}
int main() {
    scanf("%d", &k);
    for(int i = 1; i <= k; i++)
        scanf("%lld", &a[i]);
    for(int i = 1; i <= k; i++)
        scanf("%lld", &b[i]);
    for(int i = 1; i <= k; i++)
        a[i] = (a[i] % b[i] + b[i]) % b[i];
    printf("%lld", china());
    return 0;
}