数论学习总结
HeinzGuderian · · 个人记录
作为一个数学不好的OIer，对于数论我一直讳莫如深，但眼见考试临近，又不得不学，于是，我死了我开始学习数论。这导致我对高斯，欧几里得，费马等人的印象从敬仰到恨之入骨直接改观。
1.质数
质数就是除了1和它本身以外没有别的因子的数，1既不是质数也不是合数。
判断质数的几种方法：
1.试除法：对于一个数m，从2—(m-1)枚举，如果m能被其中一个数整除，那么就说明不是质数，反之是质数。
bool judge(int m)
{
if(m==1)return false;
if(m==2||m==3)return true;
for(int i=2;i<=m;i++)
if(m%i==0)return false;
return true;
} 优化:我们不难发现，若一个正整数N为合数，则存在一个整除N的数M，2≤M≤√N
证明：∵一个数N为合数，∴存在M整除N(2≤M≤n-1) 假设命题不成立，则M一定满足√N+1≤M≤N-1，则令K=N/M，满足2≤M≤n-1，原命题成立。证毕。
因此枚举到根号N就可以了：
bool judge(int m)
{
if(m==1)return false;
if(m==2||m==3)return true;
for(int i=2;i<=sqrt(m);i++)
if(m%i==0)return false;
return true;
} 2.筛法求素数
1.埃拉托斯特尼筛法，简称埃氏筛，也有人称素数筛
原理：素数的倍数一定不是素数。就是说找到一个素数，然后在给定范围内把该素数的所有倍数都标为合数，比起一个一个判断要好不少，复杂度大约为O(nloglogn)，接近线性，在10^5内跑的还算可以。
图示：
第一步:对所有2的倍数，都标记为合数。 第二步：把除了三以外的所有三的倍数标记为合数 第三步：以此类推，最终把100以内的质数筛出来
#include<bits/stdc++.h>
#define INF 10000001
using namespace std;
int prime[INF],v[INF],cnt;
void make_prime(int n)
{
memset(v,0,sizeof(v));//是否是质数，一开始全部设为是
memset(prime,0,sizeof(prime));//存储质数
for(int i=2;i<=n;i++)
{
if(v[i]==0)prime[++cnt]=i;
for(int j=i;j<=n/i;j++)
v[i*j]=1;//素数的倍数不是素数
}
return;
}
int main()
{
int n,m,x;
cin>>n;
make_prime(n);
for(int i=1;i<=cnt;i++)
{
cout<<prime[i]<<endl;
}
return 0;
}2.欧拉筛： 不难发现，埃氏筛还是有些慢，尤其是在10^6以上。因为对于一个数，比如说30，用2筛了一遍，又用3筛了一遍，又用5筛了一遍，造成了很大的时间空间浪费，所以为了解决这种情况，欧拉筛应运而生：
原理：定义一个数组v[ ],用于记录每一个合数的最小质因子，保证每一个数只被它的最小质因子筛。复杂度O(n)，在10^7内跑的很快。
代码：
int v[N],prime[N],isprime[N],cnt=0,q,n,x;
void make_prime()
{
memset(v,0,sizeof(v));
for(R i=2;i<=N;i++)
{
if(v[i]==0)
{
v[i]=i;
prime[++cnt]=i;
}
for(R j=1;j<=cnt;j++)
{
if(prime[j]>v[i]||prime[j]>N/i)break;
v[i*prime[j]]=prime[j];
}
}
}当然，还有很多其他的方法筛素数，比如：
扩展埃氏筛(比欧拉筛快)，min_25筛，洲阁筛，Pollard Rho,O(n^1/4)的期望时间复杂度,miller_rabin算法等等。可是我都不会
放上几篇篇大佬的解说：浅谈素数筛优化和素数判定方法 和最为毒瘤的Pollard Rho 算法简介最后一篇我没看qwq
练习题：P3383线性筛素数
P4718【模板】Pollard-Rho算法 （毒瘤）
素数密度
2.约数
1.要掌握整除理论和辗转相除求最大公因数，最小公倍数的辗转相除法（欧几里得算法）
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}//三目运算符版本，int gcd(int x,int y)
{
if(y==0)return x;
else return gcd(y,x%y);
}//非三目运算符版本lcm(最小公倍数)=a*b/gcd(a,b)。
int lcm(int a,int b){return (a*b)/gcd(a,b);}2.求n的正约数集合：试除法，复杂度O(√n)
int yue[1000001],cnt=0;
for(int i=1;i<=sqrt(n);i++)
{
if(n%i==0)
{
yue[++cnt]=i;
if(n/i!=i)yue[++cnt]=n/i;//约数总是成对出现的
}
}推论:一个数最多有2√n个约数。
3.求1-n每一个数的正约数集合（倍数法，复杂度O(nlogn)）
#define R register int
vector<int>yue[10000001];
void fj(int n)
{
for(R i=1; i<=n; i++)
{
for(R j=1;j<=n/i;j++)
{
yue[i*j].push_back(i);
}
}
for(R i=1; i<=n; i++)
{
for(R j=0;j<yue[i].size();j++)
{
cout<<yue[i][j]<<" ";
}
cout<<endl;
}
}推论:1-n每一个数约数个数的总和约为nlogn
例题：
Hankson的趣味题一点也不趣味
聪明的燕姿闲的没事干的燕姿
分解质因数：
int m1,m2,n1,n2,num,tot=0;
int f[10000001]={0};
int chaifen(int m1)
{
for(int i=2;i<=m1;i++)
{
if(num%i==0)
{
num/=i;tot++;
f[i]++;
if(num!=1)cout<<i<<"*";
if(num==1){cout<<i;return 0;}
chaifen(num);
}
}
}放上一篇机房大佬的笔记：数论学习笔记
3.同余问题（我死了）
1.同余:整除与同余
定义1:若整数a,b除以一个数m所得的余数相同，那么称a和b对m取模同余，记作a≡b(mod m)，并称该式子为同余式。
定义2：整数集被划分为m个不同的集合，这些集合被称为模m同余类，每个同余类中任意两个整数都是模m同余的。
例：A={2,4,6,...}是一个模2同余类，因为对于任何在这个集合中的数字，它们模2后的余数相等(都为0)定理1：a≡b(mod m),当且仅当存在整数k,使得a=b+km，这个很简单，在此不证明了
定理2：a≡b(mod m),当且仅当m|(a-b)
证明：∵a≡b(mod m)，设a%m=b%m=d(d为正整数),则有a=k1m+d,b=k2m+d.∴a-b=(k1-k2)m，∴m|(a-b).
反之，令a=k1m+d1,b=k2m+d2,a-b=(k1-k2)m+(d1-d2),得到m|(a-b)-(d1-d2)∵m|(a-b)∴d1-d2=0,即d1=d2.证毕同余的性质：
1.a≡a (mod k)
2.若a≡b (mod k),则b≡a (mod k)
3.若a≡b (mod k),b≡c (mod k),则 a≡c(mod k)//这两条有点像小学时的加法交换律和结合律
4.若a≡b(mod k),c≡d (mod k),则有:(a+c)≡(b+d)(mod k)，(a-c)≡(b-d) (mod k)，(a*c)≡(b*c)(mod k)2.欧几里得算法：∀a,b∈N，b≠0，gcd(a,b)=gcd(b,a%b)
定理一：设a,b不全为零，则存在x,y∈Z,ax+by=gcd(a,b)。证明略
裴蜀定理：对于不方程ax+by=c,当且仅当gcd(a,b)|c(即c%gcd(a,b)=0)时，方程有整数解。
证明：设x=gcd(a,b),则ax+by=x一定有整数解x1,y1,因为x|c,所以c = kx,则有c=k(a*x1+b*y1),即a*kx1+b*ky1=c,解为kx1,ky1。
反之，因为ax2+by2=c,x2,y2∈Z，∴gcd(a,b)|a,gcd(a,b)|b∴c|gcd(a,b)，证毕。欧几里得算法与扩欧的应用
2.扩展欧几里得算法(扩欧)
常常用于求不定方程ax+by=c的最小解等（因为解有无数组啊QwQ）
证明：在辗转相除求最大公因数的最后一步，此时b=0,gcd(a,b)=a.∵a1+0y=a,我们不妨让y=0(理论上y的取值对这个式子没有影响，但是在程序中可能会出现各种各样的bug，别问我为什么保险起见，让y=0吧)，这样我们就得到了该方程的一组解x=1,y=0，然后再进行扩展，最终求出原方程的解。
所以扩展欧几里得定理就是求出一组特解（比如x=1,y=0），然后进行扩展，最终回到初始状态并求出解。
void exgcd(ll a,ll b)
{
if(b==0)
{
x=1;y=15;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}