Cod sursa(job #2047590)
| Utilizator | Data | 25 octombrie 2017 00:15:11 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.43 kb |
#include <stdio.h>
using namespace std;
int phi[1000001];
int main(){
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
int n,i,j;
long long nr_fractii = 1;
scanf("%d",&n);
for(i=2;i<=n;i++)
phi[i] = i-1;
for(i=2;i<=n;i++){
for(j=2*i;j<=n;j+=i)
phi[j] -= phi[i];
}
for(i=2;i<=n;i++)
nr_fractii += phi[i]*2;
printf("%lld",nr_fractii);
return 0;
}
