hdu1787 GCD Again poj 2478 Farey Sequence 欧拉函数

时间:2024-01-07 23:11:38

hdu1787,直接求欧拉函数

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int phi(int n){
int ans=n;
for(int i=2; i*i<=n; i++)
if(n%i==0){
ans -= ans / i;
while(n%i==0) n /= i;
}
if(n>1) ans -= ans / n;
return ans;
}
int main(){
while(scanf("%d", &n)!=EOF){
if(!n) break;
printf("%d\n",n-phi(n)-1);
}
return 0;
}

poj2478,欧拉函数递推,证明可以看这里或者是算法竞赛进阶指南

\(n \log n\) 筛

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n;
long long phi[1000005];
void shai(){
for(int i=2; i<=1000000; i++)
phi[i] = i;
for(int i=2; i<=1000000; i++)
if(phi[i]==i)
for(int j=i; j<=1000000; j+=i)
phi[j] = phi[j] / i * (i - 1);
}
int main(){
shai();
for(int i=2; i<=1000000; i++)
phi[i] += phi[i-1];
while(scanf("%d", &n)!=EOF){
if(!n) break;
printf("%lld\n", phi[n]);
}
return 0;
}

线性筛:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, pri[1000005], cnt;
ll phi[1000005];
bool isp[1000005];
void shai(){
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false;
for(int i=2; i<=1000000; i++){
if(isp[i]) pri[++cnt] = i, phi[i] = i - 1;
for(int j=1; j<=cnt; j++){
if(i*pri[j]>1000000) break;
isp[i*pri[j]] = false;
if(i%pri[j]==0){
phi[i*pri[j]] = phi[i] * pri[j];//感性理解:12:1 5 7 11
break;
}
else phi[i*pri[j]] = phi[i] * (pri[j] - 1);//积性函数
}
}
}
int main(){
shai();
for(int i=2; i<=1000000; i++)
phi[i] += phi[i-1];
while(scanf("%d", &n)!=EOF){
if(!n) break;
printf("%lld\n", phi[n]);
}
return 0;
}

上面那种得到了素数,下面这种得到了最小质因子

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, pri[1000005], cnt, val[1000005];
long long phi[1000005];
void shai(){
for(int i=2; i<=1000000; i++){
if(!val[i]){
val[i] = i;
pri[++cnt] = i;
phi[i] = i - 1;
}
for(int j=1; j<=cnt; j++){
if(pri[j]>val[i] || pri[j]>1000000/i) break;
val[i*pri[j]] = pri[j];
phi[i*pri[j]] = phi[i]*(i%pri[j]?(pri[j]-1):pri[j]);
}
}
}
int main(){
shai();
for(int i=2; i<=1000000; i++)
phi[i] += phi[i-1];
while(scanf("%d", &n)!=EOF){
if(!n) break;
printf("%lld\n", phi[n]);
}
return 0;
}