2: Basic Math Algos

Learning-ACM

GCD

To Prove

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

$WLOG,\ 设a>b, g=gcd(a,b), 设a=pg, b=qg, 并且gcd(p, q)=1$
$有p>q,\ 求 gcd(p-q, q)=1$
$设p=kq+r,\ r < q,\ gcd((k-1)q+r, q)=1$
$gcd(a-b,b)=gcd((p-q)g,\ qg)=g$
$\blacksquare$

$Hence,\ gcd(a, b)=gcd(a\%b, b)$

//__gcd(a, b)
int gcd(int a, int b){ 
    return b == 0 ? a : gcd(b, a % b);
}

Complexity

$a\%b:$
$b\in [{1\over 2}a,\ a]\Rightarrow [0,\ {1\over 2}a)$
$b\in [0,\ {1\over 2}a]\Rightarrow [0,\ {1\over 2}a)$
$a减半了$
$O(log (max(a,\ b))$

LCM

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

Exgcd

$丢番图方程： ax+by=c$
$c\%gcd(a,b)!=0，无解$

//ax+by=gcd(a, b)
LL exgcd(LL a, LL b, LL& x, LL& y) {
    LL d = a;
    if(!b) x = 1, y = 0;
    else {
        d = exgcd(b, a % b, y, x);
        y = (a / b) * x;
    }
    return d;
}
//求二元一次方程x最小非负解
LL solve(LL a, LL b, LL c) {
    LL x, y, g = exgcd(a, b, x, y);
    if(c % g) return -1;
    x *= c / g;
    x = (x % b + b) % (b / g);
    return x;
}

埃氏筛法

//O(nloglogn)
bool notPrime[C];
vector<int> prime;
//int p[C / 10], ps;
for(int i = 2; i < C; ++i){
    if(notPrime[i]) continue;
    prime.push_back(i);
    for(int j = i + i; j < C; j += i)
        notPrime[j] = true;
}

欧拉筛 (线性筛)

// O(n)
bool notPrime[C];
vector<int> prime;
for(int i = 2; i < C; ++i){
    if(!notPrime[i]) prime.push_back(i);
    for(int j = 0; j < prime.size() && i * prime[j] < C; ++j){
        notPrime[i * prime[j]] = true;
        if(i % prime[j] == 0) break; 
    }
}

$下一个被筛的数就是nxt =i\times prime_{j+1}$
$break,\ i=k\times prime_j$
$nxt = k\times prime_j \times prime_{j+1}$
$nxt = prime_j\times (k\times prime_{j+1})$
$k\times prime_{j+1} > i$

质因子分解

$一个数的质因子的个数是O(logn)个$
$大于\sqrt{n}的质因子最多只有1个$

// O(sqrt(n))
void factorize(int n){
    vector<int> factors;
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0) {
            factors.push_back(i);
            while(n % i == 0) n /= i;
            if(n == 1) break;
        }
    }
    if(n != 1) factors.push_back(n);
    return factors;
}
void factorize(int n){
    vector<int> factors;
    for(int i = 0; i < primes.size() && primes[i] * primes[i] <= n; ++i){
        if(n % primes[i] == 0) {
            factors.push_back(primes[i]);
            while(n % primes[i] == 0) n /= primes[i];
            if(n == 1) break;
        }
    }
    if(n != 1) factors.push_back(n);
    return factors;
}

约数分解

$一个数的约数的个数至多有O(\sqrt{n})个$
$且一个的数的平均约数个数为O(logn)个$

void decomposite(int n){
    vector<int> divisors;
    for(int i = 2; i * i <= n; ++i){
        divisors.push_back(i);
        if(i * i != n) divisors.push_back(n / i);
    }
    return divisors;
}
vector<int> divisors[N];
void init(){
    for(int i = 2; i < N; ++i){
        for(int j = i + i; j < N; j += i) 
            divisors[j].push_back(i);
    }
}

逆元

逆元详解，点击直达
$定义：在模意义，存在一个x，满足ax\equiv 1 \mod m,\ m>1$
a * x % m == 1 % m
$我们称x为a模m的逆元，记作a^{-1}$

$a/b\%m=ab^{-1}\%m$

//MOD必须是素数
[1, MOD) 模 MOD的逆元
inv[1] = 1;
for(int i = 2; i < MOD; ++i) 
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

• $a与m互质$
  $ax+my=1$
  $ax+my \equiv 1 \mod m \Rightarrow ax \equiv 1 \mod m$

int inv(int a, int m){
    int x, y, g = exgcd(a, m, x, y);
    if(g != 1) return -1;
    return (a + m) % m;
}

• 费马小定理
  $a^{p-1} \equiv 1\mod p，p\ is\ a\ prime$
  $a\cdot a^{p-2} \equiv 1\mod p，p\ is\ a\ prime$
  $a^{-1}=a^{p-2}$

//O(logn)
int quickPow(int x, int n){
    if(n == 0) return 1;
    if(n & 1) return x * quickPow(x, n - 1);
    else {
        int ret = quick(x, n / 2); // (x^(n/2))^2 = x^n
        return ret * ret;
    }
}
//O(logn)
int quickPow(int x, int n){
    int ret = 1;
    for(; n; n >>= 1){
        if(n & 1) ret = ret * x;
        x = x * x;
    }
    return ret;
}
int inv(int x, int m){
    if(m is not a prime) return -1;
    return quickPow(x, m - 2);
}

组合数

$C_n^m:从n个物品中取出m个物品的方法数$
$A_n^m:从n个物品中取出m个物品排列成一列的方法数$

$C_n^m=\frac{n!}{m!(n-m)!}=\frac{n\cdot (n-1)\cdot(n-2)\cdots (n-m+1)}{1\cdot 2\cdot 3\cdots m}=\frac{n\cdot (n-1)\cdot(n-2)\cdots (n-(m-1))}{1\cdot 2\cdot 3\cdots m}$
$A_n^m=\frac{n!}{(n-m)!}$

int fact[N], invFact[N];
void init(){
    fact[0] = 1 = invFact[0] = 1;
    for(int i = 1; i < N; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        invFact[i] = inv(fact[i], MOD);
    }
}
//n <= MOD, m <= MOD, MOD不是很大
int C(int n, int m){
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}
//m比较小
int C(int n, int m){
    int ret = 1;
    //C(n,m)=C(n,n-m)
    m = min(m, n - m);
    for(int i = 0; i < m; ++i){
        ret *= (n - i);
        ret /= (i + 1);
    }
    return ret;
}
int C(int n, int m){
    int up = 1, dw = 1;
    //C(n,m)=C(n,n-m)
    m = min(m, n - m);
    for(int i = 0; i < m; ++i){
        up *= (n - i);
        dw *= (i + 1);
    }
    dw = inv(dw, MOD);
    return up * dw % MOD;
}
//C(n,m) = C(n-1,m)+C(n-1,m-1)
//      1
//      1 2 1
//      1 3 3 1
//n和m都不大
int C[N][N];
for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
        if(j == 0 || j == i) C[i][j] = 1;
        else C[i][j] = C[i - 1][j] + C[i - 1][j - 1];