数论¶

基础函数¶

gcd¶

设 $a/b=d, a\%b=r$

即 $a=b\times d+r$，所以 $gcd(b, r) | a$，又 $gcd(b, r) | b$，所以 $gcd(b, r) | gcd(a, b)$

又 $r=a-b\times d$，所以 $gcd(a, b) | r$，又 $gcd(a, b) | b$，所以 $gcd(a, b) | gcd(b, r)$

所以 $gcd(a, b) = gcd(b, r)$, 即 $gcd(a, b) = gcd(b, a\%b)$

一些性质

$gcd(a,b)=gcd(a,a+b)=gcd(a,ka+b)$

$gcd(ka,kb)=k*gcd(a,b)$

$gcd(a,b,c)=gcd(gcd(a,b),c)$

int gcd(int a, int b){ return b ? gcd(b, a%b) : a; }

lcm¶

int lcm(int a, int b){ return a*b/gcd(a, b); }

exgcd¶

求 $ax + by = gcd(a, b)$ 的一组整数解 x，y

b = 0时，$gcd(a, b) = a$ , x=1, y=0 为一组解

b != 0 时

设 $ax_{1} + by_{1} = gcd(a, b)$

$bx_{2}+ (a\%b)y_{2} = gcd(b, a\%b)$

因为 $gcd(a, b) = gcd(b, a\%b)$

所以 $bx_{2} + (a\%b)y_{2} = ax_{1} + by_{1}$

$a\%b = a-(a/b)*b$, 代入上式得

$bx_{2}+ ( a - (a/b) * b)*y_{2} = ax_{1} + by_{1}$

$ay_{2} + bx_{2~}- (a/b)*by_{2} = ax_{1} + by_{1}$

$ay_{2} + b[x_{2}-(a/b)*y_{2}] = ax_{1} + by_{1}$

所以 $x_{1} = y_{2}$

$y_{1} = x_{2} - (a/b)*y_{2}$

ll exgcd(ll a, ll b, ll &x, ll &y) { //返回 gcd(a, b)
    if(!b){ 
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t-(a/b)*y;
    return d;
}

快速幂¶

typedef long long ll;
ll pow(ll a, ll b, ll p) {// a^b (mod p)
    ll res = 1;
    while(b){
        if(b&1) res = res*a%p;
        a = a*a%p;
        b >>= 1;
    }
    return res;  
}

快速乘¶

//防止乘法爆ll
ll mul(ll a, ll b, ll p){
    ll res = 0;
    while(b){
        if(b&1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

素数¶

bool isprime(int x){
    if(x <= 1) return false;
    for(int i = 2; i <= x/i; i++)
        if(x % i == 0) return false;
    return true;
}

埃氏筛素数¶

bool isprime[N+1];  //0 1 是非素数
void getPrime(){
    for(int i = 2, i <= N; i++) isprime[i] = true;
    for(int i = 2; i <= N/i; i++) //如果 x>sqrt(N) 是合数， 在前面就会被筛掉
        if(isprime[i])
            for(int j = i*i; j <= N; j += i) //2i, 3i, 5i 都已经筛过，可以从i*i开始
                isprime[i] = false;     
}

欧拉筛素数(线性筛)¶

$O(n)$

int cnt = 0;
int prime[N+1];   //记录素数
bool isprime[N+1];  
void euler(){
    for(int i = 2; i <= N; i++) isprime[i] = true;
    for(int i = 2; i <= N; i++){   
        if(isprime[i]) prime[cnt++] = i;   //记录
        for(int j = 0; j < cnt && i * prime[j] <= N; j++){
            isprime[i*prime[j]] = false;
            if(i%prime[j] == 0) break;  //保证合数被最小的质因子筛去
        }
    }
}

筛区间内素数¶

//筛[l, r)之间的素数
//注意区间开闭
//如果l==1,l++，否则会认为1是素数
bool isprime_small[MAXN];   //记录前 sqrt(r) 的素数
bool isprime[MAXN];   //如果i是素数，记isprime[i-l] = true
void segement_prime(ll l, ll r){
    for(ll i = 0; i*i < r; i++) isprime_small[i] = true;
    for(ll i = 0; i < r-l; i++) isprime[i] = true;

    for(ll i = 2; i*i < r; i++)
        if(isprime_small[i]) {    //如果是素数    
            for(ll j = i*i; j*j < r; j += i) //筛[2, sqrt(b)]
                isprime_small[j] = false;
            for(ll j = max(2LL, (l+i-1)/i)*i; j < r; j += i)  //筛[a, b]
                isprime[j-l] = false; 
        }
}

Miller-Rabin 素性测试¶

bool check(ll a, ll r, ll t, ll n) {
    ll ret = pow(a, r, n), last = ret;
    for (int i = 0; i < t; i++) {
        ret = mul(ret, ret, n);
        if (ret == 1 && last != 1 && last != n - 1) return true;
        last = ret;
    }
    return ret != 1;
}

bool Miller_Rabin(ll n) {
    if (n == 2) return true;
    if (n < 2 || !(n & 1)) return false;
    ll r = n - 1, t = 0;
    while (!(r & 1)) r >>= 1, t++;
    for (int i = 1, j; i <= 8; i++) {
        ll a = rand() % (n - 2) + 2;
        if (check(a, r, t, n)) return false;
    }
    return true;
}

Pollard-Rho大数分解¶

ll pollard(ll n) {
    if (!(n & 1)) return 2;
    ll c = rand() % (n - 1) + 1;
    ll x = rand() % (n - 1) + 1, y = x, i = 1, k = 2;
    while (true) {
        i++;
        x = (mul(x, x, n) + c) % n;
        ll d = gcd(y - x + n, n);
        if (d != 1 && d != n) return d;
        if (y == x) return n;
        if (i == k) {
            y = x;
            k <<= 1;
        }
    }
}

/* 倍增优化
ll pr(ll n) {
    ll x = 0, y = 0;
    ll c = 1ll * rand() % (n - 1) + 1;
    int step = 0, goal = 1;
    ll val = 1;
    for (goal = 1;; goal <<= 1, y = x, val = 1) {
        for (step = 1; step <= goal; ++step) {
            x = (mul(x, x, n) + c) % n;
            val = mul(val, abs(y - x), n);
            if ((step % 127) == 0) {
                ll d = gcd(val, n);
                if (d > 1) return d;
            }
        }
        ll d = gcd(val, n);
        if (d > 1) return d;
    }
}
*/

ll fac[10000];
ll tot = 0;

void find_fac(ll n) {
    if (Miller_Rabin(n)) {
        fac[tot++] = n;
        return;
    }
    ll p = n;
    while (p >= n) p = pollard(p);
    find_fac(p), find_fac(n / p);
}

欧拉函数¶

定义: $\varphi(n)$表示小于等于$n$ 且与 $n$ 互质的数的个数，比如 $\varphi(1)=1$

通式：$\varphi(x)=x\prod_{i=1}^n{(1-\frac{1}{p_i})}$，其中 $p_i$是 $x$ 的所有质因数

基本性质¶

$n$ 是质数时，$\varphi(n)=n-1$
$p$ 是质数时，$\varphi(p^k)=(p-1)\times p^{k-1}$
积性性质，如果 $gcd(a,b)=1$，则$\varphi(a\times b)=\varphi(a)\times \varphi(b)$

特别的，$n$是奇数时，$\varphi(2n)=\varphi(n)$

$n > 2$ 时，$\varphi(n)$ 为偶数
$n=\sum_{d|n}\varphi(d)$
欧拉定理，若 $gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1(mod \quad m)$
扩展欧拉定理

\[ a^b\equiv \begin{cases} a^{b \% \varphi(p)}&gcd(a,p)=1 \\ a^b&gcd(a,p)\neq1,b<\varphi(p) \\ a^{b \% \varphi(p)+\varphi(p)}&gcd(a,p)\neq1,b\geq\varphi(p) \end{cases} (mod\ p) \]

求单个数的欧拉函数¶

$O(\sqrt{n})$

ll phi(ll n){
    ll res = n;
    for(ll i = 2; i*i <= n; i++){
        if(n%i==0){
            res -= res/i;
            while(n%i==0) n/=i;
        }
    }
    if(n > 1) res -= res/n;
    return res;
}

埃氏求欧拉函数¶

$\varphi(x)=x\prod_{i=1}^n{(1-\frac{1}{p_i})}$

void euler(int n){
    for (int i=1; i<=n; i++) phi[i] = i;
    for (int i=2; i<=n; i++)
        if (phi[i] == i)//这代表i是质数
            for (int j=i; j<=n; j += i)
                phi[j] = phi[j]/i*(i-1);//把i的倍数更新掉
}

欧拉筛求欧拉函数¶

$if(i\%prime[j] != 0)$，则 $i$ 与 $prime[j]$ 互质

由积性性质可得，$phi[i*prime[j]] = phi[i]*phi[prime[j]]$

$if(i\%prime[j] == 0)$，则 $i$ 中有 $i*prime[j]$ 的所有质因子，有

$\varphi(i*prime[j])=prime[j]*i*\prod_{k=1}^n{(1-\frac{1}{k_i})}=\varphi(i)*prime[j]$

int prime[maxn], cnt = 0;
bool vis[maxn];
void euler(int n){
    phi[1]=1;  //1要特判 
    for (int i=2; i < =n; i++){
        if (vis[i] == 0){  //i是质数 
            prime[cnt++] = i;
            phi[i] = i-1;
        }
        for (int j=1; j < cnt && prime[j]*i <= n; j++){
            vis[i*prime[j]] = 1;
            if (i%prime[j] == 0){
                phi[i*prime[j]] = phi[i]*prime[j];//若prime[j]是i的质因子，则根据计算公式，i已经包括i*prime[j]的所有质因子 
                break;//保证每个数只会被自己最小的因子筛掉一次 
            }
            else phi[i*prime[j]] = phi[i]*phi[prime[j]];//积性函数的性质 
        }
    }
}

中国剩余定理¶

CRT¶

洛谷 P3868

$X ≡ r_{i} ( mod\quad m_{i} )$

要求：$m_i$ 两两互质

ll CRT(ll n, ll *r, ll *m){
    ll res = 0, M = 1;
    for(int i = 0; i < n; i++) M *= m[i]; 
    for(int i = 0; i < n; i++) {
        ll x, y;
        ll tmp = M / m[i];
        ll d = exgcd(tmp, m[i], x, y);   //gcd(tmp, m[i]) = 1
        x = (x%m[i]+m[i])%m[i];  
        res = (res + tmp*x*r[i]) % M;   //可能需要用到快速乘防止溢出
    }
    return (res + M) % M;
}

EXCRT¶

洛谷 P4777

$X ≡ r_{i} ( mod\quad m_{i} )$

不要求 $m_i$ 两两互质

满足第一个条件的解为 $r_1$

假设满足前 $k-1$ 个条件的一个特解为 $res$，$M_{k-1}$ 为前 $k-1$ 个 $m$ 的 lcm

则前 $k-1$ 个方程的通解为 $$ res+x\times M_{k-1} $$ 那么对于前 $k$ 个方程,如果有解，则存在整数 $x$，使 $$ res+x\times M_{k-1}\equiv r_k\quad (mod\quad m_k) $$ 即 $$ x\times M_{k-1}\equiv r_k-res\quad (mod\quad m_k) $$

利用拓欧求解得 $x$，则前 $k$ 个方程的一个特解为 $$ res+x\times M_{k-1} $$ 通解为 $特解 + x^{'}M_k$

ll EXCRT(ll n, ll *r, ll *m){
    ll res = r[0], M = m[0];
    ll x, y;
    for(int i = 1; i < n; i++) {
        ll c = (r[i] - res%m[i] +m[i]) % m[i];
        ll d = exgcd(M, m[i], x, y), bg = m[i]/d;
        x = (x%bg+bg)%bg; 
        if(c%d != 0) return -1;  //无解,因为无法让余数扩大成c
        x = mul(x, c/d, bg);  //快速乘
        res += x*M;
        M *= bg;  //lcm
        res = (res%M+M)%M;
    }
    return res;
}

同余问题¶

逆元¶

同余不满足除法， $a/b\quad mod \quad p\quad != (a\quad mod\quad p)/(b\quad mod\quad p)$

引入 $b$ 的逆元 $x$, 即 $b*x = 1 (mod\quad p)$ ，b 与 p 互质

假设 $a/b = k (mod\quad p)$

同乘 $bx$ 得 $ a/b * bx = k * 1（mod\quad p)$

$a*x = k (mod\quad p)$

注意：b 和 p 互质，b 才有关于 p 的逆元

费马小定理求逆元¶

费马小定理：如果$p$为质数，且 $a$ 与 $p$ 互质(即 $a$ 不是 $p$ 的倍数)，则 $a^{p-1} \equiv 1 （mod\quad p)$

所以有 $a * a^{p-2} \equiv 1 (mod\quad p)$, 即 $a^{p-2} (mod\quad p)$ 是 a 的逆元

//用快速幂
ll pow(ll a, ll p){
    int res = 1;
    int d = p-2;
    while(d)    {
        if(d&1) res = res*a%p;
        a = a*a%p;
        d >>= 1;
    }
    return res;  
}

拓展欧几里得求逆元¶

如果 $b$ 与 $p$ 互质，即 $gcd(b, p) = 1$

要解 $b*x = 1 (mod\quad p)$ , 即求 $bx + yp = 1 = gcd(b, p)$ 的解 $x$

ll inv(ll b, ll p) {
    ll x, y;
    ll d = exgcd(b, p, x, y);
  return d == 1 ? (x+p)%p : -1;   //返回 -1 说明 b,p 不互质
}

欧拉函数求逆元¶

洛谷 P3811

是费小的推广，不要求 $p$ 为质数，但 $gcd(a,p)=1$

$a^{\varphi(p)}\equiv1(mod\quad p)$，所以其逆元为 $a^{\varphi(n)-1}$

ll phi(ll n){
    ll res = n;
    for(ll i = 2; i*i <= n; i++)    {
        if(n%i==0)
        {
            res -= res/i;
            while(n%i==0) n/=i;
        }
    }
    if(n > 1) res -= res/n;
    return res;
}
ans = pow(a, phi(p)-1,p);

阶乘逆元¶

求阶乘的逆元，先用费马小定理求出 n! 在 p 下的逆元，再往前推

假设 n! 的逆元为$[n!]^{-1}$, 要求 $(n-1)!$ 的逆元

$$ (n-1)! \times n[n!]^{-1} ≡ 1 (mod\quad p) $$ 所以，$(n-1)!$ 的逆元就是 $n[n!]^{-1}$

void fa_inv(ll n, ll p){
    fact[0] = 1; //factorial
    for(int i = 1; i <= n; i++) fact[i] = fact[i-1]*i % p;
    finv[N] = pow(fact[n], p-2, p);
    for(int i = n-1; i >= 0; i--)
        finv[i] = (i+1)*finv[i+1]%p;
}

线性求逆元(打表)¶

洛谷 P3811

要求出 1~n 中所有数对 $p$ 的逆元，选择打表

$1^{−1} ≡ 1 (mod\quad p)$ 设 $p = k * i + r$ 其中 1 < r < i < p, 即 $k = p/i, r = p\quad mod\quad i$

所以有 $k * i + r ≡ 0 ( mod\quad p )$

两边同时乘上 $i^{−1} * r^{−1}$

得 $k * r^{−1} + i^{−1} ≡ 0 ( mod\quad p )$

$i^{−1} ≡ −k * r^{−1} ( mod\quad p )$

得递推公式 $i^{-1} ≡ -（p/i) * (p\quad mod\quad i)^{-1} (mod\quad p)$

整理得 $inv[i] = (p - p/i) * inv[p\%i] \% p$ 其中 p % i 比 i 小

void inverse=-(int n, int p)
{
    inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = (ll)(p - p/i) * inv[p%i] % p;
}

Lucas定理¶

洛谷 P3807 HDU 3037

解决组合数取余的问题： (p必须是素数,不然不能用费马小定理求逆元) $$ C(n,m) = \prod_{i=0}^{k}{C(n_i, m_i)}(mod\quad p) $$

\[ n = n_k p^k+n_{k-1} p^{k-1}+\cdots+n_1p+n_0 \]

\[ m=m_k p^k+m_{k-1} p^{k-1}+\cdots+m_1p+m_0 \]

//预处理阶乘
void getFact(ll p) 
{
    fact[0] = 1;
    for(ll i = 1; i <= p; i++)
        f[i] = f[i-1]*i%p;
}
//计算组合数
ll comb(ll n, ll m, ll p)
{
    if(m>n) return 0;
    return fact[n]*pow(f[m],p-2, p)%p*pow(f[n-m], p-2, p)%p;  //费马小定理求逆元
}

ll lucas(ll n, ll m, ll p)
{
    if(!m) return 1;
    return lucas(n/p, m/p, p)%p*comb(n%p, m%p, p)%p;
}

BSGS¶

求 $a^x=b(mod\ \ p)$ 的 $x$ 最小的解

ll bsgs(ll a, ll b, ll p) {
    map<ll, ll> hash;
    hash.clear();
    b %= p;
    ll t = sqrt(p) + 1;
    for (ll i = 0; i < t; i++) hash[b * ksm(a, i, p) % p] = i;
    a = ksm(a, t, p);
    if (!a) return b == 0 ? 1 : -1;
    for (ll i = 1; i <= t; i++) {
        ll val = ksm(a, i, p);
        int j = hash.find(val) == hash.end() ? -1 : hash[val];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;   //无解
}

数值分析¶

Simpson 公式¶

如果原函数是次数不超过二次的多项式，可以精确计算积分值，只需要知道端点和中点的值 $$ \int_{a}^{b}{f(x)}dx \approx \frac{b-a}{6}(\quad f(a)+4f(\frac{a+b}{2})+f(b)\quad) $$

高斯约旦消元¶

洛谷 P3389

$O(n^3)$，方程数和未知数都要求是n，结果在 $a[i][n+1]$中，返回值1表示有唯一解，0表示无解

const double eps = 1e-8;
int guass_jordan(int n)
{
    for(int i = 1; i <= n; i++)
    {
        int r = i;
        for(int j = i; j <= n; j++)//把正在处理的未知数系数绝对值最大的放上来
            if(fabs(a[r][i]) < fabs(a[j][i])) 
                r = j;
        if(r != i) //交换
            for(int j = 1; j <= n+1; j++)
                swap(a[i][j], a[r][j]);
        if(fabs(a[i][i]) < eps) return 0;  //无解
        for(int j = i+1; j <= n+1; j++) a[i][j] /= a[i][i];  //系数化为1,注意i+1，如果从i开始会影响到后面
        for(int j = 1; j <= n; j++)
            if(j != i)
                for(int k = i+1; k <= n+1; k++)  //注意i+1，如果从i开始会影响到后面
                    a[j][k] -= a[i][k]*a[j][i];  
    }
    return 1;
}

其他¶

裴蜀定理¶

若 $a,b$是整数,且 $gcd(a,b)=d$，那么对于任意的整数 $x,y$, $ax+by$ 都一定是 $d$ 的倍数，即 $d|(ax+by)$

特别地，一定存在整数$x,y$，使$ax+by=d$成立。

重要推论：$a,b$互质的充要条件是存在整数 $x,y$ 使 $ax+by=1$

唯一分解定理¶

正整数$N$的标准分解式：$N=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$

那$N$的正因数个数为 $\sigma_0(N)=(1+a_1)(1+a_2)...(1+a_n)$

所有正因数的和为$\sigma_1(N)=(1+p_1+p_1^2+...+p_1^{a_1})...(1+p_n+p_n^2+...+p_n^{a_n})$

整数分块¶

$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+..+\frac{n}{n}$的和

ll ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);  //每段区间的右端点
    ans += (ll)(n / l) * (r - l + 1);
}

斯特林公式¶

\[ n! \approx \sqrt{2 \pi n}(\frac{n}{e})^n \]

用 $log10$ 快速计算大数的位数

错排公式¶

\[ f(n) = (n-1)(f(n-1)f(n-2)) \]

容斥原理¶

HDU 4135 $$ |U(A_i)|=\sum_{1\leq i\leq m}{|A_i|}-\sum_{i\leq i<j\leq m}{|A_i\bigcap A_j|}+ \dots+(-1)^{m+1}\sum|A_1\bigcap A_2\bigcap \dots\bigcap A_m| $$

void solve()
{
    int res = 0;
    for(int i = 1; i < (1<<m); i++)
    {
        int cnt = 0;
        for(int j = i; j != 0; j >>= 1) cnt += j&1;
        ll lcm = 1;
        for(int j = 0; j < m; j++)
        {
            if( (i>>j) & 1)
            {
                lcm = lcm / gcd(lcm, num[j]) * num[j];  //eg,是2的倍数不一定是4的倍数 
                if(lcm > n) break;
            }
        }
        if(cnt % 2 == 0) res -= n/lcm;
        else res += n/lcm;
    }
    cout << res;
}

Catalan数¶

设 h(n) 表示 Catalan数的第n项，$h(0) = 1, h(1) = 1$

递推式：$h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)(n\geq2)$
另类递推式：$h(n)=h(n-1)*(4*n-2)/(n+1)$
递推关系的解：$h(n)=C(2n,n)/(n+1)(n=0,1,2,...)$
递推关系的另类解：$h(n)=C(2n,n)-C(2n,n-1)(n=0,1,2,...)$

eg：进出栈，电影购票，圆内连弦，凸多边形的剖分，n对括号形成的合法括号表达式的个数， n+1个数连乘不同的乘法顺序数、

Bell数和Stirling数¶

第一类 Stirling数递推式：$S(i,j)=(i-1)*S(i-1,j)+S(i-1,j-1)$

eg：i 个不同元素构成 j 个圆排列的数目

第二类 Stirling数递推式：$S(i,j)=j*S(i-1,j)+S(i-1,j-1)$

eg：i 个不同的元素划分为 j 个非空集的方法的数目

Bell数和第二类Stirling数之间的关系：$B_n=\sum_{k=1}^n{S(n,k)}$

eg：n 个不同的数的划分方案数