P3868 [TJOI2009] 猜数字

题意：

求最小的 $n\in \mathbb{N}$，满足对于 $\forall i\in [1,k]$，有 $b_i | (n-a_i)$。

思路：

由于$b_i | (n-a_i)$ 因此$n$ $mod$ $b_i$ $=$ $a_i$ 因此这是一道exCRT的模板题 当然因为这个题保证$b_i$的数两两互质 CRT也可以做

参考代码(exCRT封装)：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ll __int128
const int N = 15;
int k, n, t;
int _a[N], _b[N];
namespace exCRT
{
    ll a, b, A, B, x, y;
    void exGCD(ll a, ll b, ll &x, ll &y)
    {
        if (b == 0)
        {
            x = 1, y = 0;
            return;
        }
        exGCD(b, a % b, x, y);
        t = x, x = y, y = t - a / b * y;
    }
    ll gcd(ll x, ll y)
    {
        return y == 0 ? x : gcd(y, x % y);
    }
    ll lcm(ll x, ll y)
    {
        return x / gcd(x, y) * y;
    }
    inline void solve()
    {
        exGCD(a, A, x, y);
        ll del = B - b, g = gcd(a, A);
        x = (x * del / g + (A / g)) % (A / g);
        ll mod = lcm(a, A);
        b = (a * x + b + mod) % mod;
        a = mod;
    }
    void main()
    {
        for (int i = 1; i <= n; i++)
        {
            A = _a[i], B = _b[i];
            if (i > 1)
                solve();
            else
                a = A, b = B;
        }
        cout << (int)(b % a) << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> _b[i];
    for (int i = 1; i <= n; i++)
        cin >> _a[i];
    exCRT::main();
}