GCDSUM - Tổng các ước chung lớn nhất
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
//#include <fstream>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define Max 1000000
using namespace std;
long long G[1000001];
int num_primes,a[100000],m,u,isprime[1000001];
int gcd(int a,int b)
{
int r;
while(b!=0)
{
r = a%b;
a = b;
b = r;
}
return a;
}
int main()
{
//freopen("GCDSUM.in","r",stdin);
int p[100000];
memset(isprime,1,sizeof(isprime));
//printf("%d",isprime[10]);
for(int i = 2;i<=1000;i++)
if(isprime[i])
{
for(int j = 2*i;j<=Max;j+=i)
isprime[j] = 0;
}
num_primes = 0;
for(int i = 2;i<=Max;i++)
if(isprime[i])
{
p[++num_primes] = i;
}
/*
for(int i = 1;i<=num_primes;i++)
{
a[i] = p[i];
if(a[i]>1000);
else
{
while(a[i]<=Max) a[i] = (a[i])*p[i];
a[i] = a[i]/p[i];
}
}
*/
//printf("%d\n",num_primes);
//printf("%d",g[78498]);
for(int i=1;i<=num_primes;i++)
{
G[p[i]]=p[i]-1;
for(int j=p[i]+p[i];j<=Max;j+=p[i])
{
if(G[j]!=0) continue;
m=j/p[i];
if(G[m]==0) continue;
int u = p[i],v = j/p[i];
while(v%p[i]==0) { v=v/p[i];u=u*p[i];}
G[j]=G[m]*p[i]+(p[i]-1)*m+G[(j/u)]*(p[i]-1)*(u/p[i]);
}
}
//printf("%d\n",num_primes);
for(int i=2;i<=Max;i++) G[i]+=G[i-1];
int n;
while(scanf("%d",&n)>0 && n>0)
{
printf("%lld\n",G[n]);
}
//getch();
}