Pagini recente » Istoria paginii utilizator/nicu19199 | Istoria paginii utilizator/thebreaker | Istoria paginii utilizator/almasim95 | Atasamentele paginii Profil XxSpeedyxXRO | Cod sursa (job #476687)
Cod sursa(job #476687)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
#define maxN 1000100
bitset <maxN> Prim;
vector < pair <int, int> > V[maxN];
int N;
int pow (int number, int exp) {
if (exp == 0)
return 1;
if (exp == 1)
return number;
int x = pow(number, exp / 2);
x *= x;
return exp % 2 == 1 ? x * number : x;
}
int main () {
int i, x, j, k, product;
long long sum = 0;
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
scanf("%d", &N);
Prim.set();
for (i = 2; i <= N; i += 2) {
Prim[i] = false;
for (x = i, j = 0; x % 2 == 0; x /= 2, j ++);
V[i].push_back(make_pair(2, j));
}
for (i = 3; i <= N; i += 2)
if (Prim[i]) {
for (j = i; j <= N; j += i) {
Prim[j] = false;
for (x = j, k = 0; x % i == 0; x /= i, k ++ );
V[j].push_back(make_pair(i, k));
}
}
for (i = 2; i <= N; ++ i) {
product = 1;
for (j = 0; j < (int) V[i].size(); ++ j)
product *= (V[i][j].first - 1) * pow(V[i][j].first, V[i][j].second - 1);
sum += product;
}
printf("%lld\n", 2LL * sum + 1);
}