数论基础学习总结（持续补充中）

数论基础

算术基本定理（唯一分解定理）

任何一个大于1的自然数都可以唯一分解成有限个素数的乘积

$N=p_1^{a_1} imes p_2^{a_2} imes... imes p_n^{a_n} | p_1<p_2<...<p_n ,a_iin Z$

上式中$p_i$为素数

有关素数筛

埃式筛法

就是拿一个已经筛选出的素数去排掉其他的数，比如2是素数，就用他筛掉2*2，2*3，2*4……，3是素数，就用他筛掉3*2，3*3，3*4……，把每个素数的倍数都筛掉，不过我们发现，3*2事实上已经在2的时候筛掉过了，即比这个数小的倍数都已经被筛过了，所以我们只要从这个数的平方开始筛就可以了。这个筛法最容易理解也最好写，一定要会写！经过这个筛法，能打素数表，能判定一个数是不是素数。复杂度O(nloglogn)。也可以用这种筛法筛出因子。

 1 const int N=1e6+7;
 2 bool isprime[N];
 3 int prime[N];//储存素数，打表
 4 void db()
 5 {
 6     memset(isprime,1,sizeof(isprime));//这步事实上不太好，不过因为是bool类型所以不影响结果
 7     isprime[0]=isprime[1]=0;
 8     int cntp=0;
 9     for(long long i=2;i<N;i++)
10     {
11         if(isprime[i])
12         {
13             prime[cntp++]=i;
14             for(long long j=i*i;j<N;j+=i)//i*i会爆int所以用ll
15                 isprime[j]=0;
16         }
17     }
18 }

埃式筛法

欧拉线性筛法

正常情况下就算是没有优化的埃式筛法应该也是够用的，但是我们发现埃式筛法还是不是最快的，比如12这个数会被2和3筛两次，诸如此类的重复会降低效率。所以我们给出欧拉线性筛法。这个筛法自然比较难理解一点，其思路是这样的，从2开始，将这个素数和之前筛出的所有素数的乘积都判负，如果碰到i是一个合数，也用他去筛，但在筛的循环中碰到一个是他因子的素数就跳出（一个合数必定能表示成至少一个素数参与的分解式），达到避免重复筛的目的，然后一个循环后就筛出了素数。这个方法比较难理解，我也不是很能感受到这个方法的正确性，不过据说用反证法能进行证明。复杂度O(n)。

线性筛还能用在处理其他积性函数上。

 1 const int N=1e6+7;
 2 bool isprime[N];
 3 int prime[N];
 4 void db()
 5 {
 6     memset(isprime,1,sizeof(isprime));
 7     isprime[0]=isprime[1]=0;
 8     int cntp=0;
 9     for(int i=2;i<N;i++)
10     {
11         if(isprime[i])
12             prime[cntp++]=i;
13     //这一部分是精髓所在也是难理解的部分，不管i是否是素数，都进循环去筛，i是合数时中途会跳出，达到减少重复筛的目的
14         for(int j=0;j<cntp&&i*prime[j]<N;j++)
15         {
16             isprime[i*prime[j]]=0;
17             if(!(i%prime[j]))
18                 break;
19         }
20     }
21 }

欧拉线性筛

有关因子

求因子个数

前置定理：若p是一个素数，a是一个正整数，那么有$ au(p^a)=a+1$。

定理：若正整数n有质因数分解$n=p_1^{a_1} imes p_2^{a_2} imes... imes p_k^{a_k}$，则$ au(n)=(a_1+1) imes(a_2+1) imes... imes(a_k+1)$。

我们需要先打出一张素数表才能套用这个。

 1 int factor_count(int n)
 2 {
 3     int ans=1;
 4     int cnt;
 5     int k=sqrt(n)+1;
 6     for(int i=0;prime[i]<k;i++)
 7     {
 8         if(n%prime[i]==0)
 9         {
10             cnt=0;
11             while(n%prime[i]==0)
12             {
13                 cnt++;
14                 n/=prime[i];
15             }
16             ans*=(cnt+1);
17         }
18     }
19     if(n>1)//这一步是因为只筛到根号n，可能会留最后一个因子，此时需要再算上这个因子
20         ans*=2;
21     return ans;
22 }

求因子个数

素因子筛

利用埃式筛法处理，复杂度O(nloglogn)

 1 const int maxn=1e5+7;
 2 void db()
 3 {
 4     vector<int> d[maxn];
 5     for(int i=2;i<maxn;i++)
 6         if(d[i].empty())
 7         {
 8             for(int j=2*i;j<maxn;j+=i)
 9                 d[j].push_back(i);
10         }
11 }

素因子筛

有关GCD

辗转相除法

1 long long gcd(long long a,long long b)
2 {
3     return b?gcd(b,a%b):a;
4 }

GCD

扩展欧几里得

 1 long long exgcd(long long a,long long b,long long &x,long long &y)
 2 {
 3     if(b==0)
 4     {
 5         x=1,y=0;
 6         return a;
 7     }
 8     long long gcd=exgcd(b,a%b,y,x);
 9     y-=a/b*x;
10     return gcd;
11 }

exgcd

欧拉定理

费马小定理

设p是质数，a是与p互质的任意整数，那么有：$a^{p-1}equiv1(mod p)$

欧拉定理

设m>1为整数，a是与m互质的任意整数，那么有：$a^{varphi(m)equiv1(mod m)}$

其中$varphi(m)$为欧拉函数，表示小于m且与m互质的正整数的个数。

欧拉降幂

$a^{x} mod m=a^{x+varphi(m) mod varphi(m)}mod m$