数论

组合数预处理

// COMB begin ----
const int N = 1e6;
vector<int> f(N), invf(N);
bool inited = 0;
int ksm(int base, int exp)
{
    int ans = 1;
    while (exp)
    {
        if (exp & 1)
        {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return ans;
}
 
int inv(int x)
{
    return ksm(x, MOD - 2) % MOD;
}
 
void pre()
{
    if (inited)
    {
        return;
    }
    inited = 1;
    f[0] = 1;
    for (int i = 1; i < N; i++)
    {
        f[i] = f[i - 1] * i % MOD;
    }
 
    invf[N - 1] = inv(f[N - 1]);
    for (int i = N - 2; i >= 0; i--)
    {
        invf[i] = invf[i + 1] * (i + 1) % MOD;
    }
}
 
int comb(int n, int k)
{
    if (!inited)
    {
        pre();
    }
    if (k < 0 or k > n)
    {
        return 0;
    }
 
    return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}
// comb end ----

快速幂

int ksm(int base, int exp)
{
    int ans = 1;
    while (exp)
    {
        if (exp & 1)
        {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return ans;
}

质数筛与最小质因子

const int N = 1e7;
 
vector<int> primes, isprime(N + 1, 1), minfactor(N + 1);
void init()
{
    isprime[0] = isprime[1] = 0;
    for (int i = 2; i <= N; i++)
    {
        if (isprime[i])
        {
            minfactor[i] = i;
            for (int j = i * i; j <= N; j += i)
            {
                isprime[j] = 0;
                if (!minfactor[j])
                {
                    minfactor[j] = i;
                }
            }
        }
    }
 
    for (int i = 2; i <= N; i++)
    {
        if (isprime[i])
        {
            primes.emplace_back(i);
        }
    }
}
 
// 返回 x 的最小质因数。调用前需要先执行 init()。
// x 必须满足 2 <= x <= N。
int getminfactor(int x)
{
    return minfactor[x];
}