Cod sursa(job #1936897)
| Utilizator | Data | 23 martie 2017 15:44:14 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.46 kb |
#include <cstdio>
#include <vector>
using namespace std;
FILE *f=fopen("fractii.in","r");
FILE *g=fopen("fractii.out","w");
int phi[1000005];
int N;
long long nr;
int main()
{
fscanf(f,"%d",&N);
for(int i=1;i<=N;i++)
phi[i]=i;
for(int i=2;i<=N;i++)
{
if(phi[i]==i)
{
for(int j=i;j<=N;j+=i)
phi[j]=phi[j]/i*(i-1);
}
nr+=phi[i];
}
nr=nr*2+1;
fprintf(g,"%lld",nr);
return 0;
}
