Existem n números de 1 a n. Preciso encontrar o cdgcd (i, n) onde i = 1 a i = n para n do intervalo 10 ^ 7. Eu usei o algoritmo de euclides para o gcd, mas deu o TLE. Existe algum método eficiente para encontrar a soma acima?

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
   ll n,sum=0;
   scanf("%lld",&n);
   for(int i=1;i<=n;i++)
   {
       sum+=gcd(i,n);
   }
   printf("%lld\n",sum);
   return 0;
}