模板区

这是用来存模板的地方，不断更新。

基础

输入优化（整数）

inline int read(){
    int num = 0, b = 1;
    char c = getchar();
    while(c < '0' || c > '9') c == '-' ? b = -1 : 0, c = getchar();
    while(c >= '0' & c <= '9') num = num * 10 + c - '0', c = getchar();
    return num * b;
}

数学

最大公约数

int gcd(int a, int b){
    if(!b) return a;
    return gcd(b, a % b);
}

快速幂

int qpow(int a, int b){                       // 分别代表底数、指数
    int t = 1;
    while(b){
        if(b & 1) t = t * a % MOD;       　　  // MOD 是模数
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

埃氏筛法

bool b[1000010];            　　　　　　　　　　// b[i] 代表 i 是否是质数
void Prime(){
    for(int i = 2; i <= 1000; i++){
        if(!b[i])
            for(int j = i; j <= 1000000; j += i)
                b[j] = 1;
    }
}

线性筛

int p[1000010], ans[1000010], cnt;                // 存储质数的序列
void Prime(){
    for(int i = 2; i <= 1000000; i++){
        if(!b[i]) ans[++cnt] = i;
        for(int j = 1; i * p[j] <= 1000000; j++){
            b[i % p[j]] = 1;
            if(i % p[j] == 0) break;
         }
    }
}

求单个数在模数为质数意义下的逆元

typedef long long ll;
ll qpow(ll a, ll b){                       　　// 分别代表底数、指数
    ll t = 1;
    while(b){
        if(b & 1) t = t * a % MOD;       　　  // MOD 是模数
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}
ll inv(ll x){
    return qpow(x, MOD - 2);
}

线性求范围内模数为质数意义下的逆元

typedef long long ll;
ll inv[1000010];
void Inv(){
    inv[0] = inv[1] = 0;
    for(ll i = 2; i <= 1000000; i++)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;    // MOD 是模数
}

数字 $aa$ 在模 $bb$ 意义下（不保证是质数）的逆元

typedef long long ll;
void exgcd(ll a, ll b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return
    }
    exgcd(b, a % b, x, y);
    y -= (a / b) * x;
}
ll inv(ll aa, ll bb){
    ll x = 0, y = 0;
    exgcd(aa, bb, x, y);
    return (x + bb) % bb;
}