持续更新~~
本篇博客包含了本蒟蒻学的数论知识点(qwq)
需要有一定基础
欧几里得算法
欧几里得算法,用于计算两个整数的最大公约数
对于两个数(a,b),我们定义(gcd(a,b))表示它们的最大公约数
为了比较快的求出最大公约数,有了以下引理:
证明:
我们设(a=xc,b=yc)其中(x,y)互质
那么(c)自然就是(a,b)最大公约数
而(a\%b=(x-ky)c)
此时我们发现(x-ky,y)互质,证明:
假设(x-ky,y)不互质,设(y=np,x-ky=mp)其中(n,m)互质
把(y=np)代入(x-ky=mp)得:
那么我们发现此时(x,y)不互质,有公约数(p),与最上面的假设相反,所以(x-ky,y)互质
那么上文提及(b=yc,a\%b=(x-ky)c)
而(y,x-ky)互质
所以(b,a\%b)的最大公约数为(c)
所以(gcd(a,b)=gcd(b,a\%b)=c)
#include<iostream>
#include<cstdio>
using namespace std;
int a,b;
int Get_gcd(int a,int b)
{
return b?Get_gcd(b,a%b):a;
}
int main()
{
scanf("%d%d",&a,&b);
printf("gcd(%d,%d)=%d
",a,b,Get_gcd(a,b));
return 0;
}
扩展欧几里得算法
扩展欧几里得算法,一般用来求解不定方程,求解线性同余方程,求解模的逆元
引理:有一组(x,y)使得:(gcd(a,b)=ax+by)
证明:
((1))、对于(b=0)的情况,(gcd(a,b)=a),那么此时(x=1,y=0)
((2))、对于(b!=0)的情况,我们根据欧几里得算法设:
因为(a\%b=a-a/b*b)
所以上式变形为:
那么我们发现每一层的情况都能由下一层递归得到,边界则为(b=0)时
那么代码如下:
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,x,y,x1,y1;
void Exgcd(int a,int b)
{
if(!b)
{
x=1;
y=0;
return;
}
Exgcd(b,a%b);
x1=y;
y1=x-a/b*y;
x=x1;
y=y1;
}
int main()
{
printf("a,b=");
scanf("%d%d",&a,&b);
Exgcd(a,b);
printf("gcd(%d,%d)=%da+%db",a,b,x,y);
return 0;
}
欧拉定理
定理:若正整数(a,n)互质,则$$a^{φ(n)}≡1 (mod n)$$
证明:
设集合(X_1,X_2,……,X_{φ(n)})为(1)到(n-1)中与(n)互质的数
那么我们思考下列数的性质:
((1))、集合中任意两个数模(n)余数一定不同
证明(反证法):
假设有 $$aX_1≡aX_2 (mod n)$$
那么必须存在
但是我们发现(a,n)互质,而(X_1-X_2)比(n)小,根据唯一分解定理可以得出上式不成立
于是我们得出结论:集合中任意两个数模(n)余数一定不同
((2))、集合中任意数模(n)与(n)互质
证明:
首先,(a,n)互质,(X_1,n)互质,那么容易得出(aX_1,n)互质,那么得到:
运用欧几里得算法得到:
也就是(aX_1\%n,n)互质
于是就得到了集合中任意数模(n)与(n)互质
那么对于下面集合
我们发现这个集合其实排序后就是:
因为那个集合数字满足取值范围在(1)到(n-1)之间(模了(n)),并且每个数与(n)互质,且两两不同,并且有(φ(n))个数(性质(1),性质(2)),这不正是上面这个集合的性质吗?
那么:
变形:
而(X_1 imes X_2 imes …… imes X_{φ(n)})与(n)互质,那么说明
欧拉定理得证
费马小定理
定理:对于质数(p),任意整数(a),均满足:(a^p≡a (mod p))
证明:
我们把式子稍微变形一下:
根据欧拉定理得到:
由于(p)是质数,所以(φ(p)=p-1),那么上式变为:
于是变回:
费马小定理得证
乘法逆元
这个东西以前以为是个什么高级的东西。。。
定义:
如果 (a imes xequiv 1 (mod p))并且(gcd(a,p)=1)(a,p互质)的话,我们称(x)是(a)在模(p)意义下的乘法逆元
求解乘法逆元方法(1):费马小定理
当(p)满足是质数的时候,我们可以用费马小定理来求解乘法逆元
费马小定理((p)为质数):
我们变形一下:
所以当(p)是质数的时候,(a)在模(p)意义下的乘法逆元为(a^{p-2}),套一个快速幂即可
这个方法对于单个查询,且(p)是质数的时候适用
方法(2):扩展欧几里得
我们首先观察一下式子:$$a imes xequiv 1 (mod p)$$
我们把它变一下也就是$$a imes x-y imes p=1$$
我们为了便于观看,把p用b代替,也就是:$$a imes x-b imes y=1$$
也就是说我们只要满足上面这个式子,那么(x)就是(a)在模(b)意义下的乘法逆元,同样的(y)就是(b)在模(a)意义下的乘法逆元
这个方法适用于单个查询
方法(3):线性算法
首先,我们知道$$1^{-1}equiv 1 (mod p)$$
我们假定(p=k imes i+r(0<r<i<p))
那么我们把这个式子放在((mod p))的意义下:$$k imes i+requiv 0 (mod p)$$
两边都乘上(i^{-1} imes r^{-1})得:$$k imes r{-1}+i{-1}equiv 0 (mod p)$$
把(k,r)替换一下:$$i^{-1}equiv -leftlfloorfrac{p}{i} ight floor imes (p mod i)^{-1} (mod p)$$
这样的话,我们就可以由前面的逆元推出后面的逆元了
这种方法适用于求一连串相邻数的逆元
例题:洛谷P3811
代码:
#include<iostream>
#include<cstdio>
#define int long long
#define N 3000000
using namespace std;
int n,p;
int inv[N];
signed main()
{
scanf("%lld%lld",&n,&p);
inv[1]=1;
for(int i=2;i<=n;++i)
inv[i]=((p-p/i)*inv[p%i])%p;
for(int i=1;i<=n;++i)
printf("%lld
",inv[i]);
return 0;
}
方法(4):线性算法(2)
以下式子都在模(p)意义下进行
我们先算出(a_i)的前缀积:$$s[i]=s[i-1] imes a_i$$
我们发现只要算出每一个前缀积的逆元(t_i),每一个(a_i)的逆元都好求了:$$a_i^{-1}=t_i imes s_{i-1}$$
那么怎么求每一个前缀积的逆元呢,我们可以先把(t_n)运用费马小定理求出来: $$t_n=s_n^{p-2}$$
再根据:$$t_i=t_{i+1} imes a_{i+1}$$
递推出所有的(t)
这个方法适用于求给出一串无规则的数的逆元
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
#define N 5000007
using namespace std;
int n,p,k;
int s[N],a[N],inv[N],inv_s[N];
int qpow(int a,int b)
{
int ans=1,res=a;
while(b)
{
if(b&1)
ans=(ans*res)%p;
res=(res*res)%p;
b/=2;
}
return ans%p;
}
signed main()
{
scanf("%lld%lld",&n,&p);
s[0]=1;
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
s[i]=(s[i-1]*a[i])%p;
}
inv_s[n]=qpow(s[n],p-2);
for(int i=n-1;i>=1;--i)
inv_s[i]=(inv_s[i+1]*a[i+1])%p;
for(int i=n;i>=1;--i)
inv[i]=(inv_s[i]*s[i-1])%p;
for(int i=1;i<=n;++i)
printf("%lld
",inv[i]);
return 0;
}
拓展:求阶乘逆元
定义(inv[i])为(i!)的逆元
首先我们知道:$$inv[i+1]=frac{1}{i+1!}$$
两边同时乘(i+1)得:$$inv[i+1] imes (i+1)=frac{1}{i!}=inv[i]$$
所以我们只要先求出(inv[n])然后往回递推出来就(ok)
欧拉函数
定义:
(φ(n))表示(1)到(n)中,与(n)互质的数的个数
特殊的(φ(1)=1)
(φ(n)=n imes prodlimits_{i=1}^k(1-frac{1}{p_i})),其中(p_i)表示(n)的质因数
证明:
因为每一个质因数(p_i)的倍数在(n)中都是均匀分布的,所以在(n)中会有(n imes frac{1}{p_i})个(p_i)的倍数,那么其余的就是(n imes (1-frac{1}{p_i}))个,每个质因数都是如此,那么最后不是所有质因数的倍数的自然就是与(n)互质的数,也就是(n imes prodlimits_{i=1}^k(1-frac{1}{p_i}))
积性函数
对于一个函数(F(x)),如果(m,n)互质,满足(F(m) imes F(n)=F(m imes n))的话,这个函数叫做积性函数,如果(m,n)不互质,而是任意整数满足上式的话被叫做完全积性函数
性质:
(1)、当(p)为质数时,(φ(p)=p-1)
证明:。。。看看定义就知道吧
(2)、当(p)为质数时,(φ(p^k)=p^k-p^{k-1})
证明:因为(p)为质数,所以:$$φ(pk)=pk imes (1-frac{1}{p})$$
因为(p^k)只有(p)这一个质因数
括号去掉就是性质(2)
(3)、欧拉函数是积性函数但不是完全积性函数,对于(m,n)互质时,有(φ(m) imes φ(n)=φ(m imes n))
(4)、当(n>2)时,(φ(n))为偶数
证明:这个是有一个基本事实:(gcd(n,p)=1,gcd(n,n-p)=1),也就是说与(n)互质的数是成对出现的,所以(φ(n))为偶数
(5)、对于小于(n)且与(n)互质的数,总和(=φ(n) imes n/2)
证明:上面已经说明了与(n)互质的数是成对出现的,每一对与(n)互质的数的平均数为((p+n-p)/2),也就是(n/2),一共有(φ(n))个与(n)互质的数,所以总和为(φ(n) imes n/2)
(6)、(n=sumlimits_{d|n}φ(d))
证明:设$$F(n)=sumlimits_{d|n}φ(d)$$
对于互质的两个数(m,n):$$F(n) imes F(m)=sumlimits_{i|m}φ(i) imes sumlimits_{j|n}φ(j)$$
因为欧拉函数是积性函数,而(m,n)互质,所以它们的所有因数都互质,所以得到:
我们发现(i_1 imes j_1,i_1 imes j_2,cdots,i_{km} imes j_{kn})刚好就是(m imes n)的所有因数,所以得到:
所以我们证明了(F(n))函数是积性函数
那么对于任何一个质数(p),我们要求(F(p^k))的时候怎么求呢?
因为(p^k)的因数只有(1,p,p^2,cdots,p^k),我们运用性质(2):
我们把(n)进行质因数分解,会得到很多质数,而它们的(F)函数就等于本身,所以:
求欧拉函数
单个:(2-sqrt n)扫一遍就好了,素数怎么求这个就怎么求
要是求<=n所有数的欧拉函数呢?
埃拉托斯特尼筛求欧拉函数 (O(n(log(n))(loglogn)))
就是普通的找质数,把倍数都筛一遍(质因数的贡献)
void Euler(int n)
{
for(int i=1;i<=n;++i)
phi[i]=i;
for (int i=2;i<=n;++i)
if (phi[i]==i)//i是质数
for (int j=i;j<=n;j+=i)//把i的倍数筛一遍
phi[j]=phi[j]/i*(i-1);
}
欧拉筛求欧拉函数 (O(n))
先来了解一下欧拉筛
for(int i=2;i<=n;++i)
{
if(!vis[i])//不是目前找到的素数的倍数
prime[cnt++]=i;//找到素数~
for(int j=0;j<cnt&&i*prime[j]<=n;++j)
{
vis[i*prime[j]]=true;//找到的素数的倍数不访问
if(i%prime[j]==0)
break;//关键!!!!
}
}
很多人对 (if(i\% prime[j]==0)) 这一句都不太理解
找到一种很好的解释:
当(i)是(prime[j])的倍数时,(i=k∗prime[j]),如果继续运算 (j+1),(i∗prime[j+1]=prime[j]∗k∗prime[j+1])
这里(prime[j])是最小的素因子,当(i=k∗prime[j+1])时会重复
这里是利用最小素因子优化,使得欧拉筛达到了优秀的线性(O(n))
下面正式求欧拉函数啦
void Euler(int n)
{
phi[1]=1;//1要特判
for (int i=2;i<=n;i++)
{
if(flag[i]==0)//这代表i是质数
{
prime[++num]=i;
phi[i]=i-1;
}
for (int j=1;j<=num&&prime[j]*i<=n;j++)//经典的欧拉筛写法
{
flag[i*prime[j]]=1;//先把这个合数标记掉
if (i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];//若prime[j]是i的质因子,则根据计算公式,i已经包括i*prime[j]的所有质因子
break;//经典欧拉筛的核心语句,这样能保证每个数只会被自己最小的因子筛掉一次
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]];//利用了欧拉函数是个积性函数的性质
}
}
}
狄利克雷卷积
数论函数
数论函数亦称算术函数,一类重要的函数,指定义在正整数集上的实值或复值函数,更一般地,也可把数论函数看做是某一整数集上定义的函数
运算
定义两个数论函数的加法为逐项相加,即: $$(f+g)(n)=f(n)+g(n)$$
定义两个数论函数的乘法为这个数与每一项相乘,即: $$(x imes f)(n)=x imes f(n)$$
狄利克雷卷积
如下:$$t(n)=sumlimits_{i|n}f(i)g(frac{n}{i})$$
性质
(1)、交换律: $$f imes g=g imes f$$
(2)、结合律:$$(f imes g) imes h=f imes (g imes h)$$
(3)、分配率:$$(f+g) imes h=f imes h+g imes h$$
(4)、(t)是积性函数
证明:设(n=a imes b),且(gcd(a,b)=1)
莫比乌斯反演
对于两个函数(F(n))与(f(n))如果满足:$$F(n)=sumlimits_{d|n}f(d)$$
通过莫比乌斯反演会得到:$$f(n)=sumlimits_{d|n} mu (d)F(frac{n}{d})$$
为什么呢?我们先来了解一下上面的(mu)函数
莫比乌斯函数
(1)、当(n=1)时,(mu (1)=1)
(2)、当(n>=2)时
((1))、(d=prodlimits_{i=1}^k p_i) (p_i)为互异素数,(mu (n)=(-1)^k)
((2))、当上面(p_i)不互异时,也就是至少有大于等于一次方的质因数时,(mu (n)=0)
所以莫比乌斯函数的性质就出来了:$$sumlimits_{d|n} mu (d)=[n=1]$$
证明莫比乌斯反演
因为性质$$sumlimits_{d|n} mu (d)=[n=1]$$
化成狄利克雷卷积形式为:$$mu imes I=epsilon$$
那么我们把莫比乌斯反演的式子拿过来:$$F(n)=sumlimits_{d|n} f(d)$$
化成狄利克雷卷积形式为:$$F=f imes I$$
两边都乘上(mu)为:$$F imes mu =f imes I imes mu$$
也就是:$$F imes mu =f imes epsilon$$
也就是:$$f=mu imes F$$
化回来就是:$$f(n)=sumlimits_{d|n} mu (d) imes F(frac{n}{d})$$
整除分块
这是一个很神奇的方法,可以把很多数论中的(O(n))的优秀复杂度优化成更优秀的(O(sqrt n))
例如下面的式子:$$sumlimits_{i=1}^n leftlfloor frac{n}{i} ight floor $$
我们本来是可以直接一次循环(O(n))算出的,但是有些题目可能会卡,所以更优秀的算法出来了
我们发现对于一部分连串的(i),(frac{n}{i})会相同
例如当(n=11)时,(i=6,7,8,9,10,11)的时候(frac{n}{i})都等于(1)
所以我们可以分一块一块来做
下面是代码:
int Get(int x)
{
int ans=0;
for(int i=1,j;i<=x;i=j+1)
{
j=x/(x/i);
ans+=(x/i)*(j-i+1);
}
return ans;
}
据说上面的复杂度是(O(sqrt n)),然而我太弱了,不会证,姑且用着吧~~~
莫比乌斯函数与欧拉函数的关系
其实应该放在上面的,但是学习没有学全面,现在才学到
首先,我们知道:$$sumlimits_{d|n} φ(d)=n$$
变形:$$sumlimits_{d|n} φ(d)=id(n)$$
变成狄利克雷卷积形式就是:$$φ imes I=id$$
我们两边都乘上(mu):$$φ imes I imes mu=id imes mu$$
我们知道(I imes mu =epsilon),带入:$$φ=id imes mu$$
化回来:$$φ(n)=sumlimits_{d|n} mu (d) id(frac{n}{d})$$
杜教筛
假设我们要求一个式子,其中(f)为积性函数:$$S(n)=sumlimits_{i=1}^n f(i)$$
那么我们构造两个积性函数:$$h=g imes f$$
展开:$$h(n)=sumlimits_{d|n} g(d) imes f(frac{n}{d})$$
两边都求和:$$sumlimits_{i=1}^n h(i)=sumlimits_{i=1}^n sumlimits_{d|i} g(d) imes f(frac{i}{d})$$
套路的换枚举项:$$sumlimits_{i=1}^n h(i)=sumlimits_{i=1}^n sumlimits_{d=1}^n [d|i] g(d) imes f(frac{i}{d})$$
除(d)把([d|i])消除:$$sumlimits_{i=1}^n h(i)=sumlimits_{d=1}^n sumlimits_{i=1}^{leftlfloor frac{n}{d} ight floor} g(d) imes f(i)$$
我们把(S(n)=sumlimits_{i=1}^n f(i))带入上式:$$sumlimits_{i=1}^n h(i)=sumlimits_{d=1}^n g(d) S(leftlfloor frac{n}{d} ight floor)$$
那么我们现在把(d=1)的提出来:$$g(1)S(n)=sumlimits_{i=1}^n h(i)-sumlimits_{d=2}^n g(d)S(leftlfloor frac{n}{d} ight floor)$$
那么我们现在就求出用杜教筛的式子了
我们举个例子:
当我们要求下式的时候:$$sumlimits_{i=1}^n mu(i)$$
我们设:$$S(n)=sumlimits_{i=1}^n mu(i)$$
那么我们就要求(S(n))
我们就要构造出两个积性函数(h,g),而我们也要使得(h,g)容易求出
我们知道:$$mu imes I=epsilon$$
那么我们就把(g=I),(h=epsilon)
这样带入上式的话,为:$$S(n)=1-sumlimits_{d=2}^n S(leftlfloor frac{n}{d} ight floor)$$
那么我们知道后面半部分可以用整除分块,那么我们预处理出(n^{frac{2}{3}})的(S),然后记忆化求出剩余的就行(可以具体看下面代码理解)
再举个例子
假如要求:$$sumlimits_{i=1}^n φ(i)$$
那么构造函数就会想到:$$φ imes I=id$$
那么带入就会得:$$S(n)=frac{n imes (1+n)}{2}-sumlimits_{d=2}^n S(leftlfloor frac{n}{d} ight floor)$$
下面给出上面两个例子的代码
美滋滋的代码时间~~~
#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>
#define N 5500007
#define ll long long
#define il inline
#define re register
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int T,n,cnt;
int sum1[N],prime[N],mu[N],phi[N];
ll sum2[N];
bool isp[N];
tr1::unordered_map<int,int> map_mu;
tr1::unordered_map<int,ll> map_phi;
il int read()
{
re int x=0,f=1; re char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
il void Get(int x)
{
mu[1]=phi[1]=1;
for(re int i=2;i<=x;++i)
{
if(!isp[i])
{
prime[++cnt]=i;
mu[i]=-1;
phi[i]=i-1;
}
for(re int j=1;j<=cnt&&(i*prime[j])<=x;++j)
{
isp[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
phi[i*prime[j]]=phi[i]*phi[prime[j]];
mu[i*prime[j]]=-mu[i];
}
}
}
for(re int i=1;i<=x;++i)
sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
il int Ans_mu(ll x)
{
if(x<=5500000)
return sum1[x];
if(map_mu[x])
return map_mu[x];
int ans=1;
for(re int l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*Ans_mu(x/l);
}
return map_mu[x]=ans;
}
il ll Ans_phi(ll x)
{
if(x<=5500000)
return sum2[x];
if(map_phi[x])
return map_phi[x];
ll ans=(x*(1+x))/2;
for(re ll l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*Ans_phi(x/l);
}
return map_phi[x]=ans;
}
int main()
{
T=read();
Get(5500000);
while(T--)
{
n=read();
printf("%lld %d
",Ans_phi(n),Ans_mu(n));
}
return 0;
}
再拓展一个例子:
我们要求:$$sumlimits_{i=1}^n i imes φ(i)$$
我们设:$$S(n)=sumlimits_{i=1}^n i imes φ(i)$$
那么我们发现不好怎么配(g,h)函数,这个时候怎么办呢,我们把(f)化为卷积形式:$$sumlimits_{d|n} (d imes φ(d))g(frac{n}{d})$$
那么我们发现(d)有点讨厌,那就要想办法消去,我们发现如果(g)函数为(id)函数的时候,(d)可以互相约去,也就是:$$sumlimits_{d|n} n imes φ(d)$$
发现(n)与(d)无关,可以提出来:$$nsumlimits_{d|n} φ(d)$$
而我们发现后面一部分就是(n),所以式子就是:$$n^2$$
那么带回去之后就是:$$S(n)=sumlimits_{i=1}^n i^2 -sumlimits_{d=2}^n d imes S(leftlfloor frac{n}{d} ight floor)$$
我们发现只要能算出平方和的话就可以求出来了
那么平方和怎么算呢?
因为(n^2=n(n+1)-n),那么得到:$$1 imes 2 -1+2 imes 3-2+3 imes 4-3+cdots +n(n+1)-n$$
移项得:$$1 imes 2+2 imes 3+3 imes 4+cdots +n(n+1)-(1+2+3+cdots +n)$$
因为(n(n+1)=frac{n(n+1)(n+2)-(n-1)n(n+1)}{3}),所以前一部分互相消去变成:$$frac{n(n+1)(n+2)}{3}$$
后一部分为:$$-frac{(1+n)n}{2}$$
原式为:$$frac{n(n+1)(n+2)}{3}-frac{(1+n)n}{2}$$
通分:$$frac{2n(n+1)(n+2)}{6}-frac{3n(1+n)}{6}$$
大功告成~~~