Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxn 1000000
using namespace std;

int f[maxn+10];
long long sumf[maxn+10];
vector<int> a;

void etf()
{
   int i,j;
   fr(i,1,maxn) f[i]=i;
   fr(i,2,maxn)
   {
     if (f[i]==i)
       for (int j=i;j<=maxn;j+=i)
         f[j]=f[j]/i*(i-1);
     sumf[i]=sumf[i-1]+f[i];
   } 
}

long long gcdsum(int n)
{
   int i,d;
   long long re=0;
   a.clear();
   a.push_back(0);
   fr(i,1,n)
     if (n/i<i) break;
     else
     {
         a.push_back(i);
         if (n/i!=i) a.push_back(n/i);
     }
   sort(a.begin(),a.end());
   fr(i,1,int(a.size())-1) re+=sumf[n/a[i]]*(a[i]+a[i-1]+1)*(a[i]-a[i-1])/2;
   return re;
}

int main()
{
   etf();
   int n;
   while (1)
   {
      scanf("%d",&n);
      if (!n) break;
      printf("%lld\n",gcdsum(n));
   }
   return 0;
}

Code mẫu của RR

#include <sstream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <queue>
#include <bitset>
using namespace std;

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i)
#define REPD(i,n) for(int i = (n)-1; i >= 0; --i)

#define DEBUG(X) { cerr << #X << " = " << (X) << endl; }
#define PR(A, n) { cerr << #A << " = "; FOR(_, 1, n) cerr << A[_] << ' '; cerr << endl; }
#define PR0(A, n) { cerr << #A << " = "; REP(_, n) cerr << A[_] << ' '; cerr << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define double long double
typedef pair<int, int> II;
#define PI (2 * acos((double)0))
#define __builtin_popcount __builtin_popcountll
#define SZ(x) ((int)(x).size())
#define ALL(a) (a).begin(), (a).end()
#define MS(a,x) memset(a, x, sizeof(a))
#define next ackjalscjaowjico
#define prev ajcsoua0wucckjsl
#define y1 alkscj9u20cjeijc
#define y0 u9cqu3jioajc

double safe_sqrt(double x) { return sqrt(max((double)0.0, x)); }
int GI(int& x) { return scanf("%lld", &x); }

const int MN = 1000111;
int phi[MN], f[MN];

void init() {
    int N = 1000 * 1000;

    // phi[i] = cnt(x: 1 <= x <= i && gcd(x, i) == 1)
    FOR(i,1,N) phi[i] = i;
    FOR(i,2,N)
        if (phi[i] == i)
            for(int j = i; j <= N; j += i)
                phi[j] -= phi[j] / i;

    // f[i] = cnt(x, y: 1 <= x, y <= i && gcd(x, y) == 1)
    f[1] = 0;
    FOR(i,2,N) f[i] = f[i-1] + phi[i];
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << (fixed) << setprecision(9);
    init();
    int n;
    while (GI(n) == 1 && n) {
        int s = 0;
        for(int i = 1; i <= n; ) {
            int q = n / i;
            int r = n / q;
            s += (r - i + 1) * (i + r) / 2 * f[q];
            i = r + 1;
        }

        cout << s << '\n';
    }
}

Code mẫu của hieult

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

Code mẫu của ll931110

{$MODE DELPHI}
Program GCDSUM;
Const
  input  = '';
  output = '';
  maxn = 1000000;
Var
  fi,fo: text;
  p,g: array [1..maxn] of integer;
  f: array [1..maxn] of int64;
  n: integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure primegens;
Var
  i,k: integer;
Begin
  Fillchar(p, sizeof(p), 0);
  For i:= 2 to maxn do if p[i] = 0 then
    Begin
      k:= 2 * i;
      While k <= maxn do
        Begin
          p[k]:= i;
          k:= k + i;
        End;
    End;
End;

Procedure gens;
Var
  i,tmp,pw: integer;
Begin
  g[1]:= 1;
  For i:= 2 to maxn do
    if p[i] = 0 then g[i]:= 2 * i - 1 else
      Begin
        tmp:= i;
        pw:= 0;

        While tmp mod p[i] = 0 do
          Begin
            tmp:= tmp div p[i];
            inc(pw);
          End;

        If tmp = 1 then g[i]:= (pw + 1) * i - pw * i div p[i] else g[i]:= g[tmp] * g[i div tmp];      
      End;

  f[1]:= 0;
  For i:= 2 to maxn do f[i]:= f[i - 1] + g[i] - i;  
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  primegens;
  gens;

  openfile;
  Repeat
    Readln(fi, n);
    If n <> 0 then writeln(fo, f[n]);
  Until n = 0;
  closefile;
End.