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();
}

P1069 [NOIP2009 普及组] 细胞分裂

题意:

求$S_i^k$ $|$ $m1^{m2}$ 时 $k_{min}$

思路:

由于$m1^{m2}$太大，我们可以提前分解它的质因数
设$m1=pri_1 * j_1+pri_2 * j_2 +\cdots +pri_n * j_n$
则$m1^{m2}=pri_1 * j_1*m2+pri_2 * j_2 *m2+\cdots +pri_n * j_n*m2$
因此$m1^{m2}$的质因数分解只需要在$m1$的基础上给每项的系数乘$m1$ 最后再对每个$S_i$作质因数分解判断即可

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 10005;
const int INF = 2e9;
int n, m1, m2, ans = INF;
int a[N];
int pri[30005], _cnt[30005], tot;
int cnt[30005];
bitset<30005> p;
inline void getPrimes(int n, int t)
{
    p.set();
    p[0] = p[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
        {
            pri[++tot] = i;
            while (t % i == 0)
            {
                t /= i;
                cnt[i] += m2;
            }
        }
        for (int j = 1; j <= tot && i * pri[j] <= n; j++)
        {
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
                break;
        }
    }
}
inline void getPrimeFac(int x)
{
    int t = a[x];
    for (int i = 1; i <= tot; i++)
    {
        _cnt[pri[i]] = 0;
        while (t % pri[i] == 0)
        {
            t /= pri[i];
            _cnt[pri[i]]++;
        }
    }
}
inline int solve()
{
    int res = -1;
    for (int i = 1; i <= tot; i++)
    {
        int now = pri[i];
        if (!cnt[now])
            continue;
        if (cnt[now] && !_cnt[now])
            return INF;
        res = max(res, (cnt[now] % _cnt[now] == 0 ? cnt[now] / _cnt[now] : cnt[now] / _cnt[now] + 1));
    }
    return (res == -1 ? INF : res);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m1 >> m2;
    if (m1 == 1)
        return cout << 0 << endl, 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    getPrimes(m1, m1);
    for (int i = 1; i <= n; i++)
    {
        getPrimeFac(i);
        ans = min(ans, solve());
    }
    cout << (ans == INF ? -1 : ans) << endl;
}

Lucas 定理

如果一口气预处理所有组合数，时间空间都是不太能接受的。因此求 $C_n^m$ 时采用公式的方法：

也就是说我们需要预处理阶乘的值与阶乘对应的逆元。

• fact[x]：$x!$
• factInv[x]：$(x!)^{-1}$

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, n, m, p;
int inv[512345];
int fact[513245];
int factInv[512345];
int C(int n, int m, int p)
{
    if (m > n)
        return 0;
    //   n!
    // m!*(n-m)!
    return fact[n] * factInv[n - m] % p * factInv[m] % p;
}
int Lucas(int n, int m, int p)
{
    if (m == 0)
        return 1;
    return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> p;
        n += m;
        inv[0] = inv[1] = 1;
        for (int i = 2; i <= p; i++)
            inv[i] = (p - p / i) * inv[p % i] % p;
        fact[0] = fact[1] = 1;
        factInv[0] = factInv[1] = 1;
        for (int i = 2; i <= p; i++)
        {
            fact[i] = fact[i - 1] * i % p;
            factInv[i] = factInv[i - 1] * inv[i] % p;
        }
        cout << Lucas(n, m, p) << "\n";
    }
    return 0;
}