Question

[Lê Minh Đức]

https://oj.vnoi.info/problem/gcdsum, mọi người giúp em với ạ

Answer 1

[💢Sosuke💢]

Tham khảo:

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