猜数字 | P3868 [TJOI2009]

前置知识

拓欧求逆元：见我的这篇
快速乘

难度

提 高 + / 省 选 − \color{cyan}提高+/省选- 提高+/省选−
C R T CRT CRT 的模板题，学到了许多技巧

题意

给定两个数组 a 1 ⋯ a k a_1 \cdots a_k a1​⋯ak​ 和 b 1 ⋯ b k b_1 \cdots b_k b1​⋯bk​
让你求出一个最小的 n n n ，使得 ∀ i ∈ [ 1 , k ] → b i ∣ ( n − a i ) \forall i\in[1,k]\rightarrow b_i \big|(n-a_i) ∀i∈[1,k]→bi​∣∣​(n−ai​)

数据范围

b i b_i bi​ 两两互素
1 ≤ k ≤ 10 1\le k\le 10 1≤k≤10
∣ a i ∣ < 1 0 9 |a_i|<10^9 ∣ai​∣<109
1 ≤ b i ≤ 6 × 1 0 3 1\le b_i\le 6\times10^3 1≤bi​≤6×103
∏ b i < 1 0 18 \prod b_i<10^{18} ∏bi​<1018

思路

• 化简所满足的式子，就是求 n ≡ a i ( m o d b i ) n\equiv a_i\pmod{b_i} n≡ai​(modbi​)
• 这个就是中国剩余定理CRT了
• 令 M = ∏ b i M=\prod b_i M=∏bi​，令 M i = M b i M_i=\frac{M}{b_i} Mi​=bi​M​，令 M i − 1 M_i^{-1} Mi−1​为模 b i b_i bi​ 意义下 M i M_i Mi​ 的逆元
• 其中必须满足 b i b_i bi​ 两两互素。
• 则最终答案为 ( ∑ i   a i M i M i − 1 ) % M \Big(\sum_i\ a_iM_iM_i^{-1}\Big)\%M (i∑​ ai​Mi​Mi−1​)%M
• 证明可以看MashiroSky：中国剩余定理学习笔记，很详细很好。
• 注意点1：里面 a i a_i ai​ 可能是负数，首先转化成取模意义下的正数。
• 注意点2：中间 a i M i M i − 1 a_iM_iM_i^{-1} ai​Mi​Mi−1​ 有的数很大，模可能达到 1 0 18 10^{18} 1018，所以直接乘会爆long long，需要使用到快速乘。
• 注意点3：中间 b i b_i bi​ 不一定是素数，所以求 M i − 1 M_i^{-1} Mi−1​ 需要使用拓欧求逆元。

核心代码

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
ll aa[20],bb[20];
ll qmul(ll a,ll b,ll mod){		/// 快速乘，可以和快速幂对比一下
    ll ans = 0;
    a = (a%mod+mod)%mod;
    if(b>a)swap(a,b);
    while(b){
        if(b&1){
            ans = (ans + a) % mod;
        }
        a = (a+a)%mod;
        b>>=1;
    }
    return ans;
}
ll ex_gcd(ll a,ll b,ll &x,ll &y){	/// 拓欧代码
    if(b==0){
        x = 1;
        y = 0;
        return a;
    }
    ll ans = ex_gcd(b,a%b,x,y);
    ll tmp = x;
    x = y;
    y = tmp - a/b*y;
    return ans;
}
ll inv2(ll a,ll mod){				/// 拓欧求逆元
    ll x,y;
    ll g = ex_gcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}
int main()
{
    int n;
    cin >> n;
    ll M = 1LL;
    for(int i = 1;i <= n;++i)cin >> aa[i];
    for(int i = 1;i <= n;++i)cin >> bb[i],M*=bb[i];
    ll ans = 0;
    for(int i = 1;i <= n;++i){
        ans = (ans + qmul(qmul(aa[i],M/bb[i],M),inv2(M/bb[i],bb[i]),M))%M;
        ans = (ans + M) % M;
    }
    cout << ans;

    return 0;
}