萌新看不少题解用了欧拉函数，这里来一篇不用欧拉函数的吧QwQ（其实本质上没什么区别，但是个人认为理解和实现起来容易一些）

题目描述

求$\sum\limits_{i=1}^n \gcd(i, n)$

算法

观察题目的性质，显然每个$gcd(i,n)$都是$n$的约数。（这一点很重要，后文的约数实际上指的是$i$和$n$的最大公约数)

于是我们可以将$n$质因数分解：

$n = p_1^{c_1} \times p_2^{c_2}\times … \times p_k^{c_k}$

然后使用算术基本定理枚举$c_i$来枚举$n$的约数。

现在问题转变为求每个$n$的约数在$gcd(i,n)$中出现了多少次。

首先，一个直接的想法就是对于$n$的一个约数$x$,直接计算有多少个数是$x$的倍数，也就是$n\div x$。

但是这很容易举出反例，比如令$n = 12$，对于约数$2$，按照刚刚的想法，则有$2$在$gcd(i,n)$中出现的次数为$6$次，分别为$2,4,6,8,10,12$

但是很明显$4$与$12$的最大公因数是$4$而非$2$，$6$,$8$,$12$也存在类似错误情况。

于是我们考虑把错误情况踢出去。

通过观察，我们发现：如果$n$的约数$x$的$y$倍（下文中的$y$均指代这个意思）与$n$的最大公因数是$x$，需要满足一个条件：

$y$的质因子不包含$x$的次数比$n$的次数低的质因子。

上面的话读起来很绕口，举个例子：

还是$n = 12 = 2^2 \times 3^1$。对于约数$2$，$2$中次数比$12$质因数分解后次数低的质因子就是$2$和$3$（$2$中包含$1$个$2$,$0$个$3$,$12$中包含$2$个$2$,$1$个$3$)，也就是说$y$中不能包含质因子$2$或$3$。

也就是上面的$4$（此时$y = 2$,包含质因子$2$),$6$（$y$包含$3$),$8$($y$包含$2$),$12$($y$包含$2$和$3$)的情况按照这个方法就都能被踢掉。

还要注意别把平次的情况去掉：

再举个例子:还是$12$，最大公约数是$4$,此时$4$与$12$的质因子$2$的次数都是$2$，所以$y$就可以包含$2$。

知道了要踢掉什么，问题就是怎么计算踢多少?

我们发现，对于$x$和$n$都含有的质因子$p_i$且$x$中的次数比$n$中的低，$x$的倍数$x \times y$中$y$不含有$p_i$的情况有$n\div x \times (p_i - 1) \times p_i$种

同时计算对答案的贡献$n\div x \times (p_i - 1) \times p_i \times x$也就是$n \times (p_i - 1) \times p_i$。

至此，本题代码就不难想了：

质因数分解$n$，$dfs$枚举每个$p_i$的次数，最后计算对答案的贡献。

(时间复杂度) $O(\sqrt{n})$

代码奉上：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

const ll N = (1 << 17) + 50;

ll n,p[N],c[N],k,c2[N],ans;

void divide(ll n)//质因数分解 
{
    for(ll i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            p[++k] = i;
            while(n % i == 0)
            {
                n /= i;
                ++c[k];
            }
        }
    }
    if(n > 1)
    {
        p[++k] = n;
        ++c[k];
    }
}

void dfs(ll cnt)//该枚举x中p_cnt的次数了 
{
    if(cnt > k)//到头了 
    {
        ll ans2 = n;
        for(ll i = 1; i <= k; i++)
        {
            if(c2[i] < c[i])//如果x中次数低与n中次数 
            {
                ans2 = ans2 / p[i] * (p[i] - 1);
            }
        }
        ans += ans2;
        return;
    }

    for(ll i = 0; i <= c[cnt]; i++)//枚举x的次数 
    {
        c2[cnt] = i;
        dfs(cnt + 1);
    }
}

int main()
{
    scanf("%lld",&n);

    divide(n);

    dfs(1);

    printf("%lld",ans);
    return 0;
}

若有错误，欢迎指出！！！