判定质数(试除法)

$O(\sqrt{n})$

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

分解质因数(试除法)

$O(\sqrt{n})$
$N = p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdots \times p_k^{\alpha_k}$

void divide(int n){
    for(int i = 2; i <= n/i; i++){ //n最多有一个大于根号n的质数 
        if(n%i==0){ //i一定是素数
            int s = 0;
            while(n%i==0){
                s++;
                n /= i; //把当前质因子除尽
            }
            cout<<i<<" "<<s<<endl;
        }
    }
    if(n > 1) cout<<n<<" "<<1<<endl; //说明这个数本身就是质数
    cout<<endl;
}

筛质数

• 欧拉筛法 $O(n)$ 用最小质因子筛合数，每个合数只筛一次，所以是线性的；
• 每个合数只有一个最小质因子；
• 多看两遍yxc的视频；
• 始终满足$pj*i$是被最小的质因子$pj$筛掉；

int p = 0;
int primes[N]={0};
int st[N]={0};
void getPrime(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[p++] = i;
        for(int j = 0; i*primes[j] <= n; j++){
            st[primes[j]*i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

求约数(试除法)

$O(\sqrt{n})$

vector<int> get_divisor(int x){
    vector<int> res;
    int sq = sqrt(x);
    for(int i = 1; i <= sq; i++){
        if(x%i==0){
            res.push_back(i);
        }
    }
    int n = res.size();
    if(sq*sq == x) n--; //x为平方数时，只能统计一次
    for(int i = n-1; i >= 0; --i){
        res.push_back(x/res[i]);
    }
    return res;
}

约数个数

$N = p_1^{\alpha_1}\times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$
约数个数 = $(\alpha_1 + 1) \times (\alpha_2 +1) \times \cdots \times (\alpha_k +1)$

for(int i = 2; i <= x/i; i++){
   while(x%i==0){
      primes[i]++; //存的当前质数的质因子个数
       x /= i;
   }
}
if(x > 1) primes[x]++; //x是质数

LL res = 1;
for(auto it: primes) res = res*(it.second + 1) % M;

快速幂

$O(logk)$

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k&1) res = (LL)res*a % p;
        k >>= 1;
        a = (LL)a*a % p;  //这里别忘了转为long long
    }
    return res;
}

$a|b$ 称为a整除b 或者 b能被a整除

快速幂求逆元

b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，$b^{m-2}$即为b的乘法逆元。
$\frac{a}{b} = a \times b^{-1} (mod \quad m)$
当m为质数时，$b^{-1} = b^{m-2}$

最大公约数

辗转相除法 欧几里得算法

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

最小公倍数

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

有理数四则运算

博客

struct Fraction{
    ll up,down;
};
Fraction f1,f2;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
Fraction reduction(Fraction result){
    if(result.down < 0){
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up==0){
        result.down = 1;
    }else{
        int d = gcd(abs(result.up), abs(result.down));
        result.up /=d;
        result.down /=d;
    }
    return result;
}
Fraction add(Fraction f1, Fraction f2){
    Fraction result;
    result.up = f1.up*f2.down+f2.up*f1.down;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction sub(Fraction f1,Fraction f2){
    Fraction result;
    result.up = f1.up*f2.down - f2.up*f1.down;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction multi(Fraction f1,Fraction f2){
    Fraction result;
    result.up = f1.up*f2.up;
    result.down = f1.down * f2.down;
    return reduction(result);
}
Fraction divide(Fraction f1,Fraction f2){
    Fraction result;
    result.up = f1.up*f2.down;
    result.down = f1.down * f2.up;
    return reduction(result);
}

扩展欧几里得

博客

int exgcd(int a, int b, int &x, int &y){
    if(b==0){
        x = 1;
        y = 0;
        return a;
    }else{
        int d = exgcd(b, a%b, x, y); //得到的x和y是下一层的 需要寻找当前层的关系
        int temp = y;
        y = x - a/b*y;
        x = temp;
        return d;
    }

}

组合数I

$O(n^2)$

//预处理 杨辉三角
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= i; j++){
            if(!j) c[i][j] = 1; //类似于杨辉三角
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % M;
        }
    }

组合数II

$O(nlogn)$

//数据上万以后 需要使用预处理阶乘和乘法逆元来处理
const int M = 1e9+7;
const int N = 100010;
int fact[N], infact[N];

fact[0] = 1;
infact[0] = 1;
for(int i = 1; i < N; i++){
    fact[i] = (LL)fact[i-1]*i % M;
    infact[i] = (LL)infact[i-1] * qmi(i, M-2, M) % M;
}

scanf("%d%d", &a, &b);
printf("%d\n", (LL)fact[a]*infact[b]%M*infact[a-b]%M);

组合数III

先求出所有分子和分母的质数及对应的质数，然后乘起来。

void get_primes(){
    for(int i = 2; i < N; i++){
        if(!st[i]) primes[k++] = i;
        for(int j = 0; j < k && primes[j]*i < N; j++){
            st[primes[j]*i] = true;
            if(i%primes[j]==0) break;
        }
    }
}
int get(int n, int x){
    int res = 0;
    while(n){
        n/=x;
        res+=n;
    }
    return res;
}

ll res = 1;
cin>>a>>b;
for(int i = 0; primes[i] <= a; i++){
    cnt[i] = get(a, primes[i]) - get(b, primes[i]) - get(a-b, primes[i]);
}
for(int i = 0; primes[i] <= a; i++){
    while(cnt[i]--) res = res*primes[i]%M;
}
cout<<res<<endl;