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();
}

Download