Hay n números del 1 al n. Necesito encontrar el ∑gcd (i, n) donde i = 1 a i = n para n del rango 10 ^ 7. Usé el algoritmo de euclides para gcd pero me dio TLE. ¿Existe algún método eficiente para encontrar la suma anterior?

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