这道题是数论题，所以需要一些变形。

考虑求所有$\gcd$的和，我们采用分组求解，也就是根据$i$和$N$的$\gcd$的值进行分组。

$$\begin{array}{ll}&\sum\limits_{i=1}^N\gcd(i,N) \\ = &\sum\limits_{d|n}d\sum\limits_{i=1}^N[\gcd(i,N)=d]\\=&\sum\limits_{d|n}d\sum\limits_{i=1}^{\frac nd}[\gcd(i,\frac Nd)=1]\\=&\sum\limits_{d|n}d\varphi(\frac Nd) \end{array}$$

于是就可以将复杂度降成根号级别的了。

然后因为$\varphi$的参数过大，不能用$\text{Euler}$筛，所以暴力用$O(\sqrt{N})$的复杂度判断。

又因为因数数量远小于$\sqrt{N}$，所以总复杂度可以承受。

这里作者比较懒，又用了根号判素数，复杂度会变大，但仍然可以承受。

1 #include 
     
       2  3 using namespace std; 4  5 #define re register 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i) 7 #define srep(i, a, b, c) for (re int i = a; i <= b; c) 8 #define repd(i, a, b) for (re int i = a; i >= b; --i) 9 #define maxx(a, b) a = max(a, b);10 #define minn(a, b) a = min(a, b);11 #define LL long long12 #define INF (1 << 30)13 14 inline LL read() {15     LL w = 0, f = 1; char c = getchar();16     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();17     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();18     return w * f;19 }20 21 const int maxn = 1e5 + 5;22 23 bool prime(LL x) {24     if (x <= 1) return false;25     rep(i, 2, sqrt(x))26         if (!(x % i)) return false;27     return true;28 }29 30 LL phi(LL x) {31     LL res = x;32     rep(i, 1, sqrt(x))33         if (!(x % i)) {34             if (prime(i)) res = res * (i-1) / i;35             if (i*i != x && prime(x/i)) res = res * (x/i-1) / (x/i);36         }37     return res;38 }39 40 LL n, ans = 0;41 42 int main() {43     n = read();44     rep(i, 1, sqrt(n))45         if (!(n % i)) {46             ans += n / i * phi(i);47             if (i * i != n) ans += i * phi(n / i);48         }49     printf("%lld", ans);50     return 0;51 }