题面：LCM求和

备用题面

你的任务是求得以下代码的值

unsigned long long allPairLcm( int n ) {
   unsigned long long res = 0;
   for( int i = 1; i <= n; i++ )
       for( int j = i + 1; j <= n; j++ )
           res += lcm(i, j); // lcm means least common multiple
   return res;
}

注意：直接实现代码可能会超时

思路

设 $S(n)=\sum_{i=1}^n\operatorname{lcm}(i,n)$ 答案就可以表示为 $ans[n]=ans[n-1]+(S(n)-n)$，这个是显然的，因为相较于原来的定义我们多算了 $\operatorname{lcm}(n,n)=n$ 的值，一会减去就可以了。

然后问题变成如何快速计算 $S(n)$，同样的从定义出发：

$\begin{aligned} \sum_{i=1}^n\operatorname{lcm}(i,n) &=\sum_{i=1}^n\frac{i\times n}{\gcd(i,n)}\\ &=n\sum_{i=1}^n\frac{i}{\gcd(i,n)} \end{aligned}$

那么接下来就是在数论中的常见变换。因为我们发现了现在化简的式子可以分为两个部分，外面的常数 $n$，里面的变量。而这个变量要如何进一步化简呢？这时候把目光放在两个地方，分子是 $i$，分母是 $\gcd(i,n)$，一般来讲的话都会觉得如果定下来了分母，那么分子是非常好计算的。

这时候就要做出一个重大的转化。我们把枚举的变量从 $i$ 变为 $\gcd(i,n)$，或者说增加一个要枚举的变量，就是 $\gcd(i,n)$ 暂借把它用字母 $d$ 表示（应该是一种习惯，感觉大家在做这类变形的时候都习惯用 $d$ 表示

式子可以变为：

$\!\begin{align} S(n) &=n\sum_{i=1}^n\frac{i}{\gcd(i,n)}\qquad\qquad\qquad\qquad\qquad\qquad\\ &=n\sum_{d\mid n}\frac{\sum_{\substack{1\le i\le n\\\gcd(i,n)=d}}i}{d}\\ &=n\sum_{d\mid n}\frac{d\times\sum_{\substack{1\le i\le \frac n d\\\gcd(i,\frac nd)=1}}i}{d}\\ &=n\sum_{d\mid n}\sum_{\substack{1\le i\le \frac n d\\\gcd(i,\frac n d)=1}}i \end{align}$

转换到这一步基本上算是完成了最抽象的推导，我对于每一个式子做一些解释。

一式没什么好说的，他就是我们第一步化简以后的式子。
二式是重要思路，因为我们决定了固定分母，那么优先在外层的 $\sum$ 中枚举 $\gcd(i,n)$，那么这时候把所有 $\gcd(i,n)$ 等于我们枚举的这个 $d$ 值的 $i$ 提出来，就会得到二式。关于其各部位的解释，大致如下：
- $d\mid n$：由于 $\gcd(i,n)$ 显然不论如何都满足 $\gcd(i,n)\mid n$ 不然的话不满足公因子的定义，这个是最外层求和符号的简单限制条件。
- $\substack{1\le i\le n\\\gcd(i,n)=d}$ 是关于上面粗略限制的进一步解释。$1\le i\le n$ 是题目中和我们给出的定义中都反复强调的变量 $i$ 的定义域，而 $\gcd(i,n)=d$ 是对于我们枚举变量的解释，以支撑起我们对于所有 $\gcd(i,n)$ 相同的任意组关于 $i$ 的分式提取公因式 $\frac{1}{\gcd(i,n)}$。
- 剩余的部分没什么好说的了，如果上面的解释看懂了应该也能理解。
三式是数论中的常规变换，因为大家的最大公因数确定了，那么不妨就直接提出来，这样可以创造出互质条件以便于进一步推导。
四式更没什么，只不过是把提出来的 $d$ 和分母抵消了而已。

经过这四步转化，基本上大家都可以看出来内部的一个和式是让我们求 $[1,\frac n d]$ 范围内所有与 $\frac n d$ 互质的数的和。而这个我们在提高组集训队和九段的欧拉函数视频课中都提到过，计算公式是：

$\sum_{i=1}^n[\gcd(i,n)=1]i=\frac{n\times\varphi(n)}{2}\quad(n\ge2)$

带入到我们的式子中，可以得到一个终极式子

$S(n)=n\sum_{d\mid n}\frac{\frac n d\times \varphi(\frac{n}{d})}{2}$

真的对了吗？细心的同志如果带入一个特殊的值，就会发现例外。当 $d=n$ 时，带入上面的式子，就会发现算出来的值应该是 $1/2$，这显然是错了，这是为什么呢？仔细看一下给出的求和公式，有一个前提条件：$n\ge 2$，而当 $d=n$ 的时候，我们带入的 $d/n=1$ 非凡了前提条件，所以这里需要额外计算 $d=n$ 的情况，汇总一下答案，就变成了：

$S(n)=n\left[\sum_{\substack{d\mid n,d\neq n}}\left(\frac{\frac n d\times \varphi(\frac{n}{d})}{2}\right)+1\right]$

回归一开始想到的递推公式 $ans[n]=ans[n-1]+(S(n)-n)$，显然的如果代入 $S(n)$ 的值，最终答案为：

$ans[n]=ans[n-1]+n\sum_{d\mid n,d\neq n}\frac{\frac{n}{d}\times\varphi(\frac n d)}{2}$

至此，所有的理论推导就都已经结束了。接下来进入代码环节。与其我们一个个枚举因子消耗大量的时间，不如在计算到这个值的时候就把它的倍数一并处理了，就像埃氏筛那样。那么轻松搞定本题~

代码

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 3000010;

ull phi[N];
ull dp[N];
ull ans[N];

void Init() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!phi[i]) {
            for(int j = i; j < N; j += i) {
                if(!phi[j]) {
                    phi[j] = j;
                }
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
    dp[1] = 1;
    for(int i = 2; i < N; i++) {
        for(int j = i; j < N; j += i) {
            dp[j] += (phi[i]) * i /  2 * j;
        }
        ans[i] = ans[i - 1] + dp[i];
    }
}

int main() {
    int T, ca = 0;
    scanf("%d", &T);
    Init();
    int n;
    while(T--) {
        scanf("%d", &n);
        printf("Case %d: %llu\n", ++ca, ans[n]);
    }
    return 0;
}