Cod sursa(job #2208484)
| Utilizator | Data | 29 mai 2018 23:33:13 | |
|---|---|---|---|
| Problema | Fractii | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.59 kb |
#include<fstream>
#define maxn 1000010
using namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
long long phi[maxn];
int N;
void calculatePhi() {
for(int i = 1; i <= N; i++)
phi[i] = i * 1LL;
for(int i = 2; i <= N; i++) {
if(phi[i] == i)
for(int j = i; j <= N; j += i) {
phi[j] /= i;
phi[j] *= (i-1);
}
}
}
int main() {
in>>N;
long long result = 1LL;
calculatePhi();
for(int i = 2; i <= N; i++)
result += phi[i];
result *= 2LL;
result -= 1LL;
out<<result;
}