欧几里得算法求最大公约数

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

最小公倍数

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

试除法分解质因数

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

朴素筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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

线性筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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

求欧拉函数

//phi(x):小于等于x的数中与x互质的有几个

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; 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 primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


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

约数个数和约数之和

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

筛法求约数个数

const int N=100010;
int prime[N],a[N],d[N],cnt; //a[i]表示最小质因子的个数,d[i]表示约数个数

bool st[N];

void get_d(int n){
    d[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[cnt++]=i;
            a[i]=1;d[i]=2;
        }
        for(int j=0;prime[j]<=n/i;j++){
            int m=prime[j]*i;
            st[m]=1;
            if(i%prime[j]==0){
                a[m]=a[i]+1;
                d[m]=d[i]/a[m]*(a[m]+1);
                break;
            } else{
                a[m]=1;d[m]=d[i]*2;
            }
        }
    }
}

筛法求约数之和

const int N=100010;
//g[i]i的最小质因子p的 p^0+p^1+p^2+...+p^k 
int prime[N],g[N],f[N],cnt;
bool st[N];

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