Cod sursa(job #1725973)
Utilizator | Ramneantu Emanuel emanuel_r | Data | 6 iulie 2016 20:57:37 |
---|---|---|---|
Problema | Fractii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.63 kb |
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int const NMax = 1000005;
int V[NMax], C[NMax];
int n;
long long sol;
void Solve()
{
int i, j, k;
f>>n;
sol = 1;
for(i=2; i<=n; i++){
sol += (i - V[i] - 1) * 2;
if(V[i] == 0)
for(j=2*i, k=1; j<=n; j+=i, k++){
V[j] += k;
C[j]++;
}
if(C[i] >= 2)
for(j=2*i, k=1; j<=n; j+=i, k++)
V[j] -= (C[j] - 1) * k;
}
g<<sol<<"\n";
}
int main()
{
Solve();
return 0;
}