欧拉函数的两种基本写法
欧拉函数有直接求法和打欧拉函数表法。
欧拉函数的定义:对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4,因为1,3,5,7均和8互质。
Euler函数表达通式:
$$ euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn) $$
,其中$-p1,p2……pn-$为x的所有素因数,x是不为0的整数。
$-euler(1)=1-$(唯一和1互质的数就是1本身)。
直接求法:
long long phi(long long x)
{
int res = x,a = x;
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
{
res = res/i*(i-1);//res -= res/i;
while(a%i==0)a/=i;
}
}
if(a>1)res =res/a*(a-1);//res -= res/a;
return res;
打表大法
#define Max 1000001
int euler[Max];
int main(){
euler[1]=1;
for(int i=2;i<Max;i++)
euler[i]=i;
for(int i=2;i<Max;i++)
if(euler[i]==i)
for(int j=i;j<Max;j+=i)
euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
}