Pagini recente » Monitorul de evaluare | Cod sursa (job #2487401) | Cod sursa (job #1571088) | Cod sursa (job #924081) | Cod sursa (job #2061194)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int divv[1000005], n, i, j;
long long tot[1000005], sol;
void makeciur(int n)
{
for(int i = 2; i * i <= n; i++) if(!divv[i])
for(int j = i * i; j <= n; j += i) divv[j] = i;
}
void maketot(int n)
{
tot[1] = 1;
sol = 1;
for(i = 2; i <= n; i++)
{
if(!divv[i]) tot[i] = i - 1;
else
{
int nr = i;
int pow = 0;
while(nr % divv[i] == 0) nr /= divv[i], pow++;
tot[i] = i / (nr * divv[i]) * tot[nr] * (divv[i] - 1);
}
sol += 2 * tot[i];
}
}
int main()
{
f >> n;
makeciur(n);
maketot(n);
g << sol << '\n';
return 0;
}