LCM Sum

求值：

易得原式如下：

(通常，我们一般会选择将化成来观察)

将原式复制一份得：

考虑到，可以将原式改为：

式中为了保证有意义，将值为的一项提取出来。

两个求和式中分母相同的项可以合并。

即：

考虑枚举，所以只需要统计的个数，因为，所以,所以满足这个条件的的数量为。

故答案为：

到这里就可以去解决这题了，但是还可以优化。

令，则有：

令，易知是积性函数，于是可以筛出。然后每次算出结果。

搜先考虑的值，有：

设，令，则：

于是有：

同理有：

解得：

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
vector<int>prime;
ll g[maxn];
bool vis[maxn];
inline void init() {
    g[1]=1;
    for(int i=2;i<maxn;++i) {
        if(!vis[i]) {
            prime.emplace_back(i);
            g[i]=(ll)i*(i-1)+1;
        }
        for(auto &j:prime) {
            if(i*j>maxn) break;
            vis[i*j]=1;
            if(i%j==0) {
                g[i*j]=g[i]+(g[i]-g[i/j])*j*j;
                break;
            }
            g[i*j]=g[i]*g[j];
        }
    }
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int T,n;
    init();
    cin>>T;
    while(T--) {
        cin>>n;
        cout<<(g[n]+1)*n/2<<'\n';
    }
    return 0;
}