Day 14学习笔记
欧拉函数
φ(n)=Σn i=1[gcd(i,n)=1]
1~n中与n互质的数的个数
例如φ(1)=1,φ(20)=8;
若q是质数，则φ(p)=p-1
性质1：
n=Σφ(n的因子)
性质2：
是积性函数。
当x,y互质时：
φ(x*y)=φ(x)*φ(y)
推导出性质：
对于p^k:(p是质数)
φ(p^k)=p^k*(p-1)/p
求φ(n):
n=p1^q1p2^q2…pk^qk
φ(n)=φ(p1^q1)φ(p2^q2)…φ(pk^qk)
=p1^q1(p1-1)/p1p2^q2*(p2-1)/p2*…pk^qk(pk-1)/pk
=n*(p1-1)/p1*(p2-1)/p2*…(pk-1)/pk
单点求φ(n)代码:
int phi(int n)
{
int ans=n,m=sqrt(n);
for(int i=2;i<=m;i++)
{
if(n%i==0)
{
ans=ans(i-1)/i;
while(n%i==0)
{
n/=i;
}
}
}
if(n>=2)
{
ans=ans*(n-1)/n;
}
return ans;
}
线性筛求欧拉函数：
p是质数
φ(1)=1;φ(p)=p-1;φ(p^k)=p^k-p^(k-1)
void phi(void)
{
phi[1]=1;
for(int i=1;i<=1000007;i++)
{
if(!vis[i])
{
prime[++cntp]=i;
phi[i]=i-1;
}
for(int j=1;prime[j]&&i*prime[j]<=1000007;j++)
{
vis[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]];
}
}
}
}
性质3：（只需了解）
φ(nm)=φ(nm/gcd(n,m))*gcd(n,m)
欧拉定理：
a^φ(n)同于1(mod n)
可用于p不是质数，但a,p互质的情况下求逆元
可用于对质数取模，降低指数规模
a^b=(a mod n)^(b mod φ(n))(mod n)
裴蜀定理：
性质：ax+by最小正整数值为r，考虑a mod r
设p=a/r向下取整，则a mod r=a-pr
带入r，得a-p(ax+by)
a=p*r+a%r
因为r|gcd(a,b)，
gcd(a,b)|r
所以r=gcd(a,b)
扩展欧几里得算法：
ax+by=gcd(a,b)
bx1+(a mod b)y1=gcd(b,a mod b)
…
gcd(a,b)xn+0yn=gcd(gcd(a,b),0)
由下一个式子的解推出上一个式子的解
考虑相邻两层：
ax1+by1=gcd(a,b)
bx2+(a mod b)y2=gcd(a,b)
gcd(a,b)=gcd(b,a%b)
ax1+by1=bx2+(a%b)y2
扩展欧几里得代码（EXGCD）:
int x,y;
void exgcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b);
int t=x;
x=y;
y=t-a/b*x;
}
求出一对解x0,y0之后，可求通解为：
x=x0+b/gcd(a,b)*t
y=y0-a/gcd(a,b)*t
(t为参数且t为整数)
中国剩余定理（孙子定理）：
给出一个数模a余b，求最小的这个数：
M=m1m2…mn
Mi=M/mi
x为最小的符合条件的值
x的通解为：x=kM+Σn i=1 aiMiti mod M
扩展中国剩余定理：（知道即可）
x common（不一定互质）=x special （互质）+i*m2/gcd(m1,m2)