【缄*默】 #数论专题# 数论知识点全面总结（更新ing）
目录
【一. 整除与约数】
1.整除的基本概念
2.取整除法
（1）取整除法的概念和应用
（2）取整除法求和
怎么计算sum{ [n/i] }？(1<=i<=n) (n<=10^13)
n太大，硬算肯定不行，我们先观察一个例子，看能否得出一些结论。
当n=20时，和式展开 20+10+6+5+4+3+2+2+2+2+1+1+1+1+1+1+1+1+1+1
注意到后面相同的数太多，不妨化简下：
20+10+6+5+1*(20-10)+2*(10-6)+3*(6-5)+4*(5-4)
=(20+10+6+5)+(20+10+6+5)-4*4
=2(20+10+6+5)-4*4
这样，复杂度就从O(n)降为O(√n)了。
3.因子和约数
（1）基础概念
- 平凡因子：1和自身。
- 若p是质数，则p没有非平凡因子。
- 若p没有非平凡因子，则p是质数。
（2）求N的正约数集合——试除法
约数总是成对出现的。只需要扫描因子d=1~√n。
int factor[1600],m=0;
for(int i=1;i*i<=n;i++){
if(n%i==0){
factor[++m]=i;
if(i!=n/i) factor[++m]=n/i;
}
}
for(int i=1;i<=m;i++)
cout<<factor[i]<<endl;（3）试除法的推论
一个整数N的约数个数上界，为2√N。
（4）求1~N每个数的正约数集合——倍数法
vector<int>factor[500010];
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)
factor[i*j].push_back(i);
for(int i=1;i<=n;i++){
for(int j=0;j<factor[i].size();j++)
printf("%d ",factor[i][j]);
printf("\n");
}（5）倍数法的推论
1~N每个数的约数个数总和，大约为N*logN。
【例题】洛谷 p1403 约数研究
< 法1 > 倍数法筛因子个数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*【洛谷p1403】约数研究【法1：倍数法筛因子个数】
f(n)表示n的约数个数，现在给出n，要求求出f(1)到f(n)的总和。 */
int p[1000100],n;
void reads(int &x){ //读入优化（正负整数）
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f; //正负号
}
void init(){ //倍数法求因数个数
memset(p,0,sizeof(p));
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)
p[i*j]++;
}
int main(){
int sum=0; reads(n); init();
for(int i=1;i<=n;i++) sum+=p[i];
printf("%d\n",sum);
}< 法2 > 归纳统计法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*【洛谷p1403】约数研究
f(n)表示n的约数个数，现在给出n，要求求出f(1)到f(n)的总和。 */
void reads(int &x){ //读入优化（正负整数）
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f; //正负号
}
int main(){
int n,sum=0; reads(n);
for(int i=1;i<=n;i++) sum+=n/i;
printf("%d\n",sum);
}
【例题】 bzoj 1053 Antiprime数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
/*【bzoj1053】caioj 1411 打牌
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。
例如，整数1，2，4，6等都是反质数。
现在给定一个数N，你能求出不超过N的最大的反质数么 */
/*【分析】通过计算可以得出，
一个2000000000以内的数字不会有超过12个素因子。
并且小素因子多一定比大素因子多要优。
所以，预处理出前12个素数直接搜索即可。*/
ll n,ans=1,num=1;
int p[15]={1,2,3,5,7,11,13,17,19,23,29,31};
void dfs(ll k,ll now,ll cnt,ll last){
if(k==12){ //已有12个质因子
if(now>ans&&cnt>num){
ans=now; num=cnt;
} //↑↑↑更多因子，数更大，更新ans、num
if(now<=ans&&cnt>=num){
ans=now; num=cnt;
} //↑↑↑更多因子，数反而更小，更新ans、num
return;
}
int t=1;
for(int i=0;i<=last;i++){ //枚举每个质因子的范围
dfs(k+1,now*t,cnt*(i+1),i);
t*=p[k]; //质因子个数++
if(now*t>n) break; //达到now最大的情况
}
}
int main(){
scanf("%d",&n); dfs(1,1,1,31);
printf("%d",ans); return 0;
}
4. 最大公约数与最小公倍数
（1）欧几里得算法：求最大公约数
先推断出更相相损的公式a-b，a不断减b相当于a%b。
int gcd(int a,int b){ //欧几里得算法，O(log(a+b)).
if(b==0) return a;
else return gcd(b,a%b);
}【练习】noip 2009 Hankson的趣味题
- 已知正整数a0,a1,b0,b1,设某未知正整数x满足：
- 1． x 和 a0 的最大公约数是 a1；
- 2． x 和 b0 的最小公倍数是 b1。
- Hankson的“逆问题”就是求出满足条件的正整数x。
- 但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。
- 因此他转而开始考虑如何求解满足条件的x的个数。
【分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
/*【noip2009】Hankson的趣味题
已知正整数a0,a1,b0,b1,设某未知正整数x满足：
1． x 和 a0 的最大公约数是 a1；
2． x 和 b0 的最小公倍数是 b1。
Hankson的“逆问题”就是求出满足条件的正整数x。
但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。
因此他转而开始考虑如何求解满足条件的x的个数。*/
/*【分析】分解质因数。
首先，不难得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。
对于某质因数y，a0含有a0c个y，a1含有a1c个y（或，b0含有b0c个y，b1含有b1c个y）。
a0c<a1c，无解；a0c=a1c，x至少含有a1c个y；a0c>a1c，x只可能含有a1c个y。
[ 求出对于每一个质数，x可能含有几个它 ]，并求出一共有多少种选择方式。
根据乘法原理，将每一个质数的方案数相乘，即得到答案。*/
const int MAXSIZE=5000;
int prime_table[MAXSIZE]; //素数表
int prime_table_size; //素数个数
void initialize_prime_table(){ //素数表
prime_table_size=0;
prime_table[prime_table_size++]=2;
for(int i=3; prime_table_size<MAXSIZE; i++){
bool is_prime=true;
for(int j=0;j<prime_table_size;j++)
if(i%prime_table[j]==0){ //其实可以用筛法啊...
is_prime=false; break;
}
if (is_prime) prime_table[prime_table_size++]=i;
}
}
void calculate_one_step(int& a0,int& a1,int& b0,int& b1,int& result,int p){
int a0c=0,a1c=0,b0c=0,b1c=0;
while(a0%p==0) a0/=p,a0c++; //对每个质数，寻找a0c，a1c
while(a1%p==0) a1/=p,a1c++;
while(b0%p==0) b0/=p,b0c++;
while(b1%p==0) b1/=p,b1c++;
if(a0c<a1c||b0c>b1c) result*=0; //无解
else if(a0c==a1c&&b0c==b1c){
if(a1c<=b1c) result*=b1c-a1c+1;
//↑↑↑ x至少含有b1c-a1c+1个y因子，用乘法原理记录答案
else result*=0; //无解
}
else if(a0c==a1c&&b0c<b1c){
if(a1c<=b1c) result*=1;
else result*=0; //无解
}
else if(a0c>a1c&&b0c==b1c){
if (a1c<=b1c) result*=1;
else result*=0; //无解
}
else{ //if(a0c>a1c&&b0c<b1c)
if(a1c==b1c) result*=1; //x只可能含有a1c个y
else result*=0; //无解
}
}
int calculate(int a0,int a1,int b0,int b1){
//gcd(x/a1,a0/a1)=1; gcd(b1/x,b1/b0)=1;
if(a0%a1!=0||b1%b0!=0) return 0;
int result=1;
for(int i=0;i<prime_table_size;i++)
calculate_one_step(a0,a1,b0,b1,result,prime_table[i]);
if (a0!=1) calculate_one_step(a0,a1,b0,b1,result,a0);
else if (b1!=1&&b1!=a0) calculate_one_step(a0,a1,b0,b1,result,b1);
return result;
}
int main(){
initialize_prime_table();
int n,a0,a1,b0,b1; scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
printf("%d\n",calculate(a0,a1,b0,b1));
}
return 0;
}
（2）二进制算法：求最大公约数
对于两个数的最大公约数gcd(m, n)，有：
m<n时，gcd(m, n)=gcd(n, m)
m偶n偶时，gcd(m, n)=2*gcd(m/2, n/2)
m偶n奇时，gcd(m, n)=gcd(m/2, n)
m奇n偶时，gcd(m, n)=gcd(m, n/2)
m奇n奇时，gcd(m, n)=gcd(n, m-n)
/* 【二进制算法——大整数求最大公约数】
对于两个数的最大公约数gcd(m, n)，有：
1.m<n时，gcd(m, n)=gcd(n, m)
2.m偶n偶时，gcd(m, n)=2*gcd(m/2, n/2)
3.m偶n奇时，gcd(m, n)=gcd(m/2, n)
4.m奇n偶时，gcd(m, n)=gcd(m, n/2)
5.m奇n奇时，gcd(m, n)=gcd(n, m-n) */
void gcd(int a[],int b[],int t){ //传入两个高精度数组
if(cmp(a,b)==0){ T=t; return; } //a,b相等（用cmp函数来比较数组相等）
if(cmp(a,b)<0){ gcd(b,a,t); return; } //a<b时，gcd(a,b)=gcd(b,a)
int ta,tb; //↓↓↓div(a,2):a/=2，这里只是为了标记奇偶数
if(a[1]%2==0){ div(a,2); ta=1; } else ta=0;
if(b[1]%2==0){ div(b,2); tb=1; } else tb=0;
if(ta&&tb) gcd(a,b,t+1); //都是偶数,gcd(a,b)=2*gcd(a/2,b/2)
else if(!ta&&!tb) //都是奇数
{ minus(a,b); gcd(a,b,t); } //minus(a,b):a=a-b
else gcd(a,b,t); //上述3、4条
}【练习】高精度版最大公约数
（3）互质的概念与性质
（4）最小公倍数
（5）扩展欧几里得算法
用于解不定方程 ax+by=d ，乘法逆元...
a、裴蜀定理
↑↑↑ 较难证明，需要记住。
裴蜀定理的推论：
b%a=b-a*[ b/a(下取整) ] 。接下来将a、b的因数合并：
那么可以得到一组新的解 --->（多次）无穷多组解。
那么新的一组解可以表示为：
b、线性同余
线性同余方程（模线性方程）是最基本的同余方程，即：ax≡b (mod n)，
其中a、b、n都为常量，x是未知数，一定的转化后得到：ax = kn + b,
这里的k为任意整数，于是我们可以得到更加一般的形式即：ax + by + c = 0，
这个方程就是二维空间中的直线方程，但是x和y的取值为整数，
所以这个方程的解是一些排列成直线的点集。
c、同余方程求解
求解同余方程第一步是转化成一般式：ax + by = c，这个方程的求解步骤如下：
首先求出a和b的最大公约数d = gcd(a, b)，那么原方程可以转化成d(ax/d + by/d) = c，
容易知道(ax/d + by/d)为整数，如若d不能整除b，方程必然无解，算法结束；否则进入 ii 。
由 i 可以得知，方程有解则一定可以表示成 ax + by = c = gcd(a, b)*c’，
那么我们先来看如何求解d = gcd(a, b) = ax + by，根据欧几里德定理，
有：d = gcd(a, b) = gcd(b, a%b) = bx’ + (a%b)y’ = bx’ + [a-b*(a/b)]y’ = ay’ + b[x' - (a/b)y']，
于是有x = y’, y = x’ – (a/b)y’。
由于gcd(a, b)是一个递归的计算，所以在求解(x, y)时，
(x’, y’)其实已经利用递归计算出来了，递归出口为b == 0的时候，
（对比辗转相除，也是b == 0的时候递归结束），那么这时方程的解x0 = 1, y0 = 0。
int gcd(int a,int b,int &x,int &y){
if(a==0){ //gcd(0,b)=b,显然0*0+1*b=b满足条件，得到一组解
x=0; y=1; return b; //更新解x、y，且找到了最大公约数
}
int d=gcd(b%a,a,y,x);
//↑↑新的一组解中，交换了x、y的顺序
//↓↓得出新解：x=x0-[b/a(下取整)]*y0; y=y0;
x-=(b/a)*y; return d;
}
【例题】洛谷 p2520 向量
- 给你一对数a,b，你可以任意使用(a,b),(a,-b),(-a,b),
- (-a,-b),(b,a),(b,-a),(-b,a),(-b,-a)这些向量，
- 问你能不能拼出另一个向量(x,y)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*【洛谷p2520】向量
给你一对数a,b，你可以任意使用(a,b),(a,-b),(-a,b),
(-a,-b),(b,a),(b,-a),(-b,a),(-b,-a)这些向量，
问你能不能拼出另一个向量(x,y)。*/
ll t,a,b,x,y,k;
inline int in(){ //读入优化
ll a=0;char x=getchar();bool f=0;
while((x<'0'||x>'9')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=1;
while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
return f?-a:a;
}
inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
inline bool check(ll x,ll y){ return x%k==0 && y%k==0; }
int main(){
t=in(); while(t--){
a=in(),b=in(),x=in(),y=in();
k=gcd(a,b)*2;
if(check(x,y)||check(x+a,y+b)||check(x+b,y+a)||check(x+a+b,y+a+b))
printf("Y\n");
else printf("N\n");
}
return 0;
}
【二. 素数】
（1）基本概念和算法
质数（素数）：在大于1的自然数中，除了1和它本身以外不再有其他因数的数。
特殊：1既不是素数也不是合数。
（2）质数筛法
1.普通筛法
2.埃式筛法
直接用【质数的倍数】去判断后面的 vis数组。
3.欧拉筛法（线性筛法）
（3）唯一分解定理
唯一分解定理用于判断质因数分解：
质因数分解代码实现：
三. 同余系与剩余系
1. 同余的概念和性质
2.1 剩余系与剩余定理
可以得到公式：（注意：一般要开 long long）
2.2 中国剩余定理（CRT）
（下面的部分需要用到乘法逆元的知识，相关知识在下面...）
（注意，mi是上面方程组中每个被模出来的余数。）
对于排队的数据：M=105；
M1=35， a1=2，t1=2；
M2=21， a2=3，t2=1；
M3=15， a3=2，t3=1；
所以：ans=(140+63+30)%105=23。
3. 乘法逆元
原数（5的剩余系）： 0 1 2 3 4
逆元（从余数中寻找）： x 1 3 2 4
注意：当且仅当m为素数时，每个数都有唯一的一个乘法逆元。
（在费马小定理中会有证明......）
4. 费马小定理
当上述证明中取1的时候，a*a^(p-2) = 1 (mod p)。
此时p为质数。所以 a^(p-2) 即为 a 的乘法逆元。
即：当且仅当p为素数时，有唯一的一个乘法逆元。
其中的 a^(p-2) 可以用快速幂求出。
5. 欧拉定理
6. 欧拉函数
7. 积性函数的性质和应用
f(ab)=f(a)*f(b) 可用于分解因式求函数值。
——时间划过风的轨迹，那个少年，还在等你。