Есть n чисел от 1 до n. Мне нужно найти cgcd (i, n), где i = 1 - i = n для n из диапазона 10 ^ 7. Я использовал алгоритм Евклида для gcd, но он дал TLE. Есть ли эффективный способ найти вышеуказанную сумму?

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