数论学习总结（2021.05.10-2021.05.16）

判定质数

①试除法
②埃氏筛、线性筛

//线性筛打质数表
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int prime[N],vis[N],cnt;

void get_prime(int x){
    for(int i=2;i<=x;i++){
        if(!vis[i])
            prime[++cnt] = i;
        for(int j=1;prime[j]<=x/i;j++){
            vis[i*prime[j]] = 1;
            if(i%prime[j] == 0)
                break;
        }
    }
}
int main(){
    int n;
    cin>>n;
    get_prime(n);
    for(int i=1;i<=cnt;i++)
        cout<<prime[i]<<' ';
}

③巨大质数的判断
判断n是否为质数时，枚举多个质数a，对于每个枚举的a，满足gcd(n,a) = 1且 $a^{n-1} \equiv 1(mod\quad n)$ ，有一个a不满足则n不是质数

分解质因数

//分解质因数
#include<bits/stdc++.h>
using namespace std;
map<int,int> M;

void calc(int x){
    for(int i=2;i<=x/i;i++){
        while(x%i == 0){
            M[i]++;
            x/=i;
        }
    }
    if(x > 1)   //x中最多有一个大于根号x的质因子
        M[x]++;
}
int main(){
    int n;
    cin>>n;
    calc(n);
    for(auto k:M)
        cout<<k.first<<' '<<k.second<<endl;
}

暴力求约数：只筛质因子+dfs爆搜

试除法求所有约数

//求一个数所有的约数
#include<bits/stdc++.h>
using namespace std;
set<int> S;

void calc(int x){
    for(int i=1;i<=x/i;i++)
        if(x%i == 0){
            S.insert(i);
            S.insert(x/i);
        }
}
int main(){
    int n;
    cin>>n;
    calc(n);
    for(auto k:S)
        cout<<k<<endl;
}

唯一分解定理

$N=P_1^{\alpha_1}\cdot P_2^{\alpha_2}\cdot \cdots P_n^{\alpha_n}$
P1、P2、......Pn为N的质因子

n的约数个数： $(\alpha_1 +1)(\alpha_2 +1)\cdots(\alpha_n +1)$

n的约数之和： $(P_1^{0}+P_1^{1}+\cdots+P_1^{\alpha_1}) (P_2^{0}+P_2^{1}+\cdots+P_2^{\alpha_2}) \cdots (P_n^{0}+P_n^{1}+\cdots+P_n^{\alpha_n})$

求1~n所有数的约数个数和： $\frac{n}{1}+\frac{n}{2}+\cdots+\frac{n}{n}$

①1的倍数有N/1个（同理1是N/1个数的约数）
②2的倍数有N/2个
③N的倍数有N/N个

整除分块（数论分块）：

以n==8为例：
图片说明
求1~N所有数的约数个数和或者所有数的约数和不需要逐个计算，可以分块计算，最多可分为 $2\sqrt{n}$ 个块（不做证明，可查资料），一个块的r=n/(n/l)

扩展欧几里得算法

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

有整数解的条件：c%gcd(a,b) == 0

解出来的x1、y1为ax+by = gcd(a，b)的特解
ax+by=c的特解为x1*c/gcd(a,b)、y1*c/gcd(a,b)

通解：x=x1+b/dt ， y=y1-a/dt(t为任意整数)

欧拉函数：1~n中与n互质的数的个数称为欧拉函数，记作 $\phi(n)$

根据唯一分解定理： $\phi(n)=n(1-\frac{1}{P_1})(1-\frac{1}{P_2})\cdots(1-\frac{1}{P_n})$

分解质因数过程中求欧拉函数：

//公式法求欧拉函数
#include<bits/stdc++.h>
using namespace std;
int calc(int x){
    int cnt=x;
    for(int i=2;i<=x/i;i++){
        if(x%i == 0)
            cnt = cnt/i*(i-1);
        while(x%i == 0)
            x /= i;
    }
    if(x > 1)
        cnt = cnt/x*(x-1);
    return cnt;
}
int main(){
    int n;
    cin>>n;
    cout<<calc(n)<<endl;;
}

筛法求欧拉函数：

#include<bits/stdc++.h>
using namespace std;
int phi[100],vis[100],prime[100];

void calc(int x){
    phi[1] = 1;
    int cnt=0;
    for(int i=2;i<=x;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;prime[j]<=x/i;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j] == 0){
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]] = phi[i]*(prime[j]-1);
        }
    }
}
int main(){
    int n;
    cin>>n;
    calc(n);
    for(int i=1;i<=n;i++)
        cout<<phi[i]<<endl;
}