程序
#include <bits/stdc++.h>
#define sc(p) scanf("%d",&p)
const int N=10000100;
using namespace std;
int phi[N],prime[N]; bool vis[N];
void init (int gd)
{
phi[1]=1;
for (int i=2; i<=gd; i++)
{
if (!vis[i]) prime[++prime[0]]=i,phi[i]=i-1;
for (int j=1; j<=prime[0]; j++)
{
long long k=prime[j]*i;
if (k>gd) break;
vis[k]=1;
if (i%prime[j]==0)
{
phi[k]=phi[i]*prime[j];
break;
}
else phi[k]=phi[i]*phi[prime[j]];
}
}
}
int main()
{
int n; sc(n); init (n);
return 0;
}
线性筛
一个O(n)筛质数的东东，思想是每个数都只用其最小的质因子去筛（程序已包含在上）。
欧拉函数
欧拉函数φ(n)（念phi）表示1~n中与n互质的数的个数。
\(φ(n)=n\prod_{d|n}(1-\frac{1}{d})(d为质数)\)
（证明省略四万字）
性质
1.$φ(1)=1$
2.$当p为质，φ(p)=p-1$
3.$当gcd(a,b)=1,φ(ab)=φ(a)·φ(b)$（积性函数）
4.$当p为质，φ(p^{k})=(p-1)p^{k-1}$
（程序见上）
应用
欧拉定理
$若gcd(a,m)=1,a^{φ(m)}\equiv 1(mod \quad m)$
$当m为质，则a^{m-1}\equiv 1(mod \quad m)$，又称费马小定理
求逆元
一个数a模m意义下的逆元，记为$a^{-1}$，满足$a·a^{-1}\equiv 1(mod \quad m)$。
只有a与m互质情况下才有逆元。
由欧拉定理知$a^{φ(m)}\equiv 1(mod \quad m)$
故$a^{-1}=a^{φ(m)-1}$
降幂
当gcd(a,m)=1,$a^b\equiv a^{b\%φ(m)}(mod \quad m)$
否则$a^b\equiv a^{b\%φ(m)+φ(m)}(mod \quad m)$
推论
n以内与n互质的数是成对出现的，即若a<n，有$gcd(a,n)=1\Leftrightarrow gcd(n-a,n)=1$
滋磁
%%罗梓璋
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：线性筛和欧拉函数”