题目描述
给出一个n，求1-n这n个数，同n的最小公倍数的和。
例如：n = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。
由于结果很大，输出Mod 1000000007的结果。
输入
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000)
第2 - T + 1行：T个数A[i](A[i] <= 10^9)
输出
共T行，输出对应的最小公倍数之和
输入样例
3
5
6
9
输出样例
55
66
279
题解
\[\begin{aligned}
&n\sum{\frac{i}{(i,n)}}\\
&=n\sum_{d|n}{\sum_{i=1}^n{\frac{i}{d}}}[(i,n)=d]\\
&=n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[(i,\frac{n}{d})=1]\\
&=n\sum_{d|n}φ(\frac{n}{d})\frac{n}{2d}\\
&=\frac{n}{2}\left(\sum_{d|n}φ(d)d+1\right)\\
\end{aligned}
\]
&n\sum{\frac{i}{(i,n)}}\\
&=n\sum_{d|n}{\sum_{i=1}^n{\frac{i}{d}}}[(i,n)=d]\\
&=n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[(i,\frac{n}{d})=1]\\
&=n\sum_{d|n}φ(\frac{n}{d})\frac{n}{2d}\\
&=\frac{n}{2}\left(\sum_{d|n}φ(d)d+1\right)\\
\end{aligned}
\]
考虑\(\sum_{d|n}φ(d)d\)是个积性函数。
证明：
\[\begin{aligned}
&设x,y互质\\
&\sum_{d|n}φ(d)d=1*(φ·id)\\
&1*(φ(x)·x\timesφ(y)·y)=1*(φ(xy)·xy)
\end{aligned}
\]
则对于每个p，都有
\[\sum_{d|p}φ(d)d=1+(p-1)*p=p^2-p+1
\]
\]
p的x次方也类似。根据唯一分解定理，我们可以得到下面的推论：
\[\begin{aligned}
&设f(n)=\sum_{d|n}φ(d)d\\
&f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})
\end{aligned}
\]
&设f(n)=\sum_{d|n}φ(d)d\\
&f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})
\end{aligned}
\]
我们知道\(φ\)函数的一个性质：对于\(n=p^k\)，有\(φ(p^k)=p^k-p^{k-1}\)。所以可以预处理质数，然后来分解质因数，对每个质因子算出\(f(p_i^{c_i})\)，然后乘起来就好了。（这样复杂度是\(O(\frac{\sqrt{n}}{\log n})\)的，如果不先预处理质数就是\(O(\sqrt{n})\)的，会TLE）
这样子的话常数也是很小的，在51nod跑到了第一页（rk17）。
个人感觉这个做法好写好想啊...为什么网上都没这个做法的题解...都是好麻烦的考虑贡献
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define il inline
namespace io {
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')
#define I_int ll
inline I_int read() {
I_int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
char F[200];
inline void write(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int
}
using namespace io;
using namespace std;
const ll mod = 1e9 + 7;
#define N 1000010
int T = read();
int p[N], cnt;
bool vis[N];
void init(int n) {
cnt = 0;
for(int i = 2; i <= n; ++i) {
if(!vis[i]) p[++cnt] = i;
for(int j = 1; j <= cnt && i * p[j] <= n; ++j) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
ll power(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod; b >>= 1;
} return ans;
}
ll inv2 = power(2, mod-2);
ll solve(ll n) {
ll ans = 1;
for(int i = 1; p[i] * p[i] <= n && i <= cnt; ++i) {
if(n % p[i] == 0) {
ll now = 1, sum = 1;
while(n % p[i] == 0) {
n /= p[i];
now *= (ll)p[i];
sum += (ll)(now - now / p[i]) * now;
}
ans = ans * sum % mod;
}
}
if(n > 1) {ans = ans * (1 + n * (n - 1) % mod) % mod;}
return ans + 1ll;
}
int main() {
init(35000);
while(T--) {
ll n = read();
outn(solve(n)*(n*inv2%mod)%mod);
}
}