https://www.spoj.pl/problems/GCDEX/
#include <cstdio>
using namespace std;
const int N = 1000001;
bool sifted[N] = {};
int primes[80000], nprimes = 0;
long long gcdsum[N];
int main()
{
int n;
gcdsum[0] = 0;
gcdsum[1] = 1;
for (int i = 2; i < N; ++i)
{
if (!sifted[i])
{
primes[nprimes++] = i;
gcdsum[i] = 2*i-1;
}
for (int j = 0; j < nprimes && i*primes[j] < N; ++j)
{
sifted[i*primes[j]] = true;
if (i%primes[j] == 0)
{
int n = i*primes[j], m = 0, nn = 1;
while (n%primes[j] == 0)
n /= primes[j], ++m, nn *= primes[j];
gcdsum[i*primes[j]] =
((m+1)*nn-m*(nn/primes[j])) * gcdsum[n];
break;
}
gcdsum[i*primes[j]] = gcdsum[i]*gcdsum[primes[j]];
}
}
for (int i = 1; i < N; ++i)
gcdsum[i] += gcdsum[i-1]-i;
while (scanf("%d", &n), n)
printf("%lld\n", gcdsum[n]);
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
