数学知识上

试除法判定质数

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

分解质因数

void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int s =0 ;
            while(n%i==0) s++,n/=i;
            printf("%d %d\n",i,s);
        }
    }
    if(n>1) printf("%d %d\n",n,1);
    puts("");
}

筛选质数
https://www.acwing.com/solution/AcWing/content/3776/

埃式筛法
int cnt = 0;
int primes[MAXCNT];
void get_primes(int n) {
    for(int i =2;i<=n;i++){
        if(!st[i]){
            primes[cnt++] = i;
            for(int j = i;j<=n;j+=i){
                st[j] = true;
            }
        }
    }
}
时间复杂度o(nloglogn)


void get_prime(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;
        }
    }
    return;
}
时间复杂度 o(n)

欧拉函数
1～N中与N互质的数的个数称为欧拉函数。
N = p1^a1 * p2^a2 * p3^a3..
则phi(N) = N(1-1/p1)(1-1/p2)*(1-1/p3)...

1. 从N中去掉p1,p2,p3..的所有倍数
2. 加上p1&p2的倍数，p2&p3的倍数，p3&p4的倍数...
3. 减去所有pi&pj&pk的倍数...
4. 加上所有pi& pj & pk & pl 的倍数...

欧拉定理

int res = 1;
for(int i=2;i<=n/i;i++){
    if(n%i==0){
        res = res / i * (i-1);
        n/=i;
    }
    if(n>1) res = res * n / (n-1);
    cout << res << endl;
}

筛法求欧拉函数

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

若a与n互质，则a^phi[n] = 1 mod n
欧拉定理的证明：
与n互质的数有phi[n]个，分别为a[1],a[2]...a[phi[n]]
a[1],a[2],a[3],a[4],a[phi[n]]
令b[1] = a*a[1], b[2] = a*a[2], b[3] = a*a[3]...
if(b[i] == b[j]) 可以推导出 a[i]等于a[j],所以不相同。。
然后根据容斥原理，可以得到这一组数是原来那组数的一个排列。
所以b[1]*b[2]...b[n] = a[1]*a[2]...*a[n];
然后可得到 a^[phi[n]] mod n = 1;
欧拉定理得证。

快速幂

LL qmi(int a,int b){
    LL res = 1;
    while(b){
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}

快速幂求逆元

a,b要互质
那么用快速幂 a^[b-2]求可以求了它的逆元了。