线性筛欧拉函数
欧拉函数
在数论,对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目,用(varphi(n))表示。
通式: $ varphi(x)=xprodlimits_{i=1}^{n}{(1-frac{1}{p_i})} $
其中(p_1, p_2……p_n)为(x)的所有质因数,(x)是不为0的整数。
性质:
- $ varphi(1)=1 $
- 当正整数p为质数时 $ varphi(n)=n-1 $
- 欧拉函数是积性函数,当a与b互质时,满足 $ varphi(a imes b)=varphi(a) imes varphi(b) $
- 当p为质数时 $ varphi(p^k)=p^k-p^{k-1}=(p-1) imes p^{k-1} $ 因为除了p的倍数外,其他数都跟n互质。
- 当n为奇数时,$ varphi(2n)=varphi(n) $,证明与上述类似。
- 当(n>2)时,$ varphi(n) $都是偶数
两种代码(都能顺便筛素数)
- 第一种写法 类似于埃氏筛法 (O(nsqrt{n})?),
不推荐
int euler[maxn];
void euler_init(){
euler[1]=1;
for(int i=2;i<maxn;i++)
euler[i]=i; //初始化
for(int i=2;i<maxn;i++)
if(euler[i]==i) //判断是否为质数 若euler[i]!=i说明已经进行过运算了
for(int j=i;j<maxn;j+=i)
euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
- 第二种写法 欧拉筛改版(O(n))
int prime[1000010],phi[1000010],cnt=0;
bool vis[10000010];
void Euler(int n)
{
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
phi[i]=i-1;//①
}
for(int j=1;j<=cnt;j++)
{
if(i*prime[j]>n)break;
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=prime[j]*phi[i];//②
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);//③
}
}
}
- ①,参见性质2
- ②,参见通式
若i%prime[j]==0,则
[egin{split}varphi(i imes prime[j]) =i imes prime[j] imes prodlimits_{i=1}^{n}{(1-frac{1}{p_i})} =prime[j] imes varphi(i)end{split}
]
- ③,参见性质2和性质3
若i%prime[j]!=0,则
[varphi(i imes prime[j])=varphi(i) imes varphi(prime[j])=varphi(i) imes (prime[j]-1)
]
欧拉定理
若n,a为正整数,且n,a互质,则$ a^{varphi(n)} equiv 1 pmod n $
当n为质数时,即为费马小定理$ a^{n-1} equiv 1 pmod n$
应用
求解乘法逆元,若a,n互质,则
$ a^{varphi(n)} equiv 1 pmod n\ Rightarrow a^{varphi(n)-1} imes a equiv a^{-1} imes a pmod n\ Rightarrow a^{varphi(n)-1} equiv a^{-1} pmod n(
所以,a的在模n意义下的乘法逆元等于) a^{varphi(n)-1} $