Cod sursa(job #1929414)
Utilizator | Tir Vlad Ioan Vlad3108 | Data | 17 martie 2017 16:47:54 |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.51 kb |
#include <cstdio>
#define PHI 1000005
using namespace std;
int phi[PHI];
inline long long Phi(int n){
long long S=1;
for(int i=2;i<=n;++i)
phi[i]=i-1;
for(int i=2;i<=n;++i){
S+=2*phi[i];
for(int j=2*i;j<=n;j+=i)
phi[j]-=phi[i];
}
return S;
}
int main(){
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
int n;
scanf("%d",&n);
printf("%lld\n",Phi(n));
fclose(stdin);fclose(stdout);
return 0;
}