$$ 质数 $$

$$ 试除筛质数 $$

#include<cstdio>
using namespace std;

int primes(int n)
{
    for(int i = 2;i <= n / i;i ++)
        if(n % i == 0) return false;
    return true;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n --){
        int x;
        scanf("%d",&x);
        if(primes(x) == false) puts("No");
        else puts("Yes");
    }
    return 0;
}

$$ 试除求质因子 $$

#include<cstdio>

using namespace std;

void get_num(int x)
{
    for(int i = 2;i <= x / i;i ++)
        if(x % i == 0)
        {
            int sum = 0;
            while(x % i == 0) x /= i, sum ++;
            printf("%d %d\n",i, sum);
        }
    if(x > 1) printf("%d %d\n",x,1);
    puts(" ");
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n --)
    {
        int x;
        scanf("%d",&x);
        get_num(x);
    }
    return 0;
}

$$ 朴素筛质数 $$

#include<cstdio>
using namespace std;
const int N = 1e4;

int prime[N],cnt,n;
bool st[N]; 

void get_primes(int n)
{
    for(int i = 2;i <= n;i ++){
        if(!st[i]) prime[cnt ++] = i;
        for(int j = i + i; j <= n;j += i)
            st[j] = true;
    }
}

int main(){
    scanf("%d",&n);

    get_primes(n);

    for(int i = 0;i < cnt;i ++)
        printf("%d ", prime[i]);

    puts("");

    printf("%d", cnt);

    return 0;
}

$$ 线性质数筛 $$

#include<cstdio>
using namespace std;

const int N = 1e5;

int prime[N],n,cnt;
bool st[N];

void get_primes(int n)
{
    for(int i = 2;i <= n;i ++){
        if(!st[i]) prime[cnt ++] = i;
        for(int j = 0; prime[j] <= n / i;j ++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    scanf("%d",&n);

    get_primes(n);

    for(int i = 0;i < cnt;i ++){
        printf("%d ",prime[i]);
    }

    puts(" ");

    printf("%d", cnt);

    return 0;
}

$$欧几里得算法 / gcd / 最大公约数$$

#include<cstdio>
using namespace std;

int n;

int gcd(int a,int b)
{
    return b ? gcd(b, a % b) : a;
}
int main()
{
    scanf("%d",&n);
    while(n --)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n", gcd(x,y));
    }
    return 0;
}

$$ 欧拉函数 $$ $$ (朴素) $$

#include<cstdio>
using namespace std;

int n;

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

    return res;
}

int main()
{
    scanf("%d",&n);

    printf("%d",phi(n));

    return 0;
}

$$ 欧拉函数 $$ $$ (筛法) $$

#include<cstdio>

using namespace std;

const int N = 1e5 + 10;

int res = 0,cnt, n;
int prime[N]; //质数 
int euler[N]; //每个数的欧拉函数值 
bool st[N];

void get_eulers(int n){
    euler[1] = 1;
    for(int i = 2;i <= n;i ++)
    {
        if(!st[i]){
            prime[cnt ++] = i;
            euler[i] = i - 1;
        }
        for(int j = 0;prime[j] <= n / i;j ++){
            int t = prime[j] * i;
            st[t] = true;
            if(i % prime[j] == 0)
            {
                euler[t] = euler[i] * prime[j];
                break;
            }
            euler[t] = euler[i] * (prime[j] - 1);
        }
    }
}

int main()
{
    scanf("%d", &n);

    get_eulers(n);

    for(int i = 1;i <= n;i ++)
        res += euler[i];

    printf("%d\n", res);

    return 0;
}

$$ 快速幂 $$ $$ (位运算) $$

#include<cstdio>

using namespace std;

int n;

typedef long long LL;

int qmi(int a,int k,int p)
{
    if(p == 1) return 0;

    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    while(n --){
        int a,k,p;
        scanf("%d%d%d",&a,&k,&p);
        printf("%d\n",qmi(a,k,p));
    }
    return 0;
}

$$ 扩展欧几里得算法 $$ $$ (edgcd) $$

#include<cstdio>

using namespace std;

int d;

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main(){
    int n;
    scanf("%d",&n);
    while(n --){
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        int d = exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }

    return 0;
}

$$ 组合数 $$

$$ C_n^m = C_{n - 1}^{m} + C_{n - 1}^{m - 1} $$

求法一：递推

数据范围：$ 1 < T < 10 ^ 5$, $ 1 < a, b <2000 $

根据： $ C_n^m = C_{n - 1}^{m} + C_{n - 1}^{m - 1} $ 递推式得到如下代码：

#include<cstdio>
using namespace std;
const int N = 2001, mod = 1e9 + 7;
int n;
int c[N][N];
void init(){ //预处理
    c[1][1] = c[0][1] = 1;
    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 - 1] + d[i - 1][j]) % mod;
}
int main()
{
    init();

    scanf("%d",&n);

    while(n --){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",c[a][b]);
    }

    return 0;
}

解法二：快速幂 $ + $ 逆元

数据范围： $ 1 < T < 10 ^ 4$,$ 1 < a, b < 10^6 $

#include<cstdio>
using namespace std;
const int N = 1e5+10,mod = 1e9+7;
typedef long long LL;
int n;
int f[N],inf[N];

int imp(int a,int k,int q){
    LL res = 1;
    while(k){
        if(k&1) res = (LL)res * a % q;
        a = (LL)a * a % q;
        k >>= 1;
    }
    return res;
}

void init(){
    f[0] = inf[0] = 1;
    for(int i = 1;i < N;i ++){
        f[i] = (LL)f[i - 1] * i % mod;
        inf[i] = (LL)inf[i - 1] * imp(i, mod - 2, mod) % mod;
    }
}

int main(){
    init();

    scanf("%d",&n);

    while(n --){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",(LL)f[a] * inf[b] % mod * inf[a - b] % mod);
    }

    return 0;
}

解法三： 卢卡斯定理($ The $ $law $ $ of $ $lucas $)

数据范围: $ 1 < T < 20$, $ 1 < a, b < 10^{18} $, $ 1 < p < 10^8 $

$$ {{C_a^b} \equiv C_{a \mod\ p}^{b \mod \ {p}} \cdot C_{a / p}^{b / p}(\mod p)}$$

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long LL;

int p;

int imp(int a,int k){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a,int b){
    int res = 1;
    for(int i = 1,j = a;i <= b;i ++,j --){
        res = (LL)res * j % p;
        res = (LL)res * imp(i, p - 2) % p;
    }
}

int lucas(LL a,LL b){
    if(a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main(){
    int n;

    scanf("%d",&n);

    while(n --){
        LL a,b;
        scanf("%lld%lld",&a,&b,&p);
        printf("%lld\n",lucas(a,b));
    }

    return 0;
}

解法四：分解质因数$ + $高精

数据范围：$ 1 <a, b< 5000 $

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 5010;

int prime[N],cnt;
bool st[N];
int sum[N];

vector<int> mul(vector<int> a,int b){
    vector<int>c;

    int t = 0;

    for(int i = 0;i < a.size(); i++){
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while(t){
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

int work(int n,int p){
    int res = 0;
    while(n){
        res += n / p;
        n /= p;
    }  
    return res;
}

void get_prime(int n){
    for(int i = 2;i <= n;i ++){
        if(!st[i]) prime[cnt ++] = i;
        for(int j = 0; prime[j] <= n / i;j ++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main(){
    int a,b;
    scanf("%d%d",&a,&b);

    get_prime(a);

    for(int i = 0;i < cnt;i ++){
        int p = prime[i];
        sum[i] = work(a, p) - work(b, p) - work(a - b, p);
    }

    vector<int> res;
    res.push_back(1);

    for(int i = 0; i < cnt;i ++){
        for(int j = 0;j < sum[i];j ++){
            res = mul(res, prime[i]);
        }
    }

    for(int i =res.size() - 1;i >= 0;i --){
        printf("%d",res[i]);
    }

    return 0;
}