难题
题意
定义 \(f(i)\) 为非 \(i\) 因数的最小正整数，给出 \(n\)，求 \(\sum_{i=1}^{n} f(i) \bmod 10^9+7\)。
思路
显然 \(f(i) \ge 2\)。
若 \(f(i)=x\)，则 \(f(i)\) 一定为 \(\text{lcm}(1,2,\dots,x-1)\) 的倍数，但不是 \(\text{lcm}(1,2,\dots,x)\) 的倍数。
可以枚举 \(x\)，统计有多少个数的答案为 \(x\)，即：
\[ans=\sum_{x=2}x\times (\lfloor\frac{n}{\text{lcm}(1,2,\dots,x-1)}\rfloor-\lfloor\frac{n}{\text{lcm}(1,2,\ldots,x)}\rfloor) \]化简一下可以得到：
\[ans=2n+\sum_{x=2} \lfloor \frac{n}{\text{lcm}(1,2,\dots,x)}\rfloor \]代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
signed main() {
freopen("math.in", "r", stdin);
freopen("math.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
int n, ans, l = 1; cin >> n;
ans = 2 * n % mod;
for (int i = 2; ; i ++) {
l = lcm(l, i);
ans += (n / l), ans %= mod;
if (l > n) break;
}
cout << ans << "\n";
}
return 0;
}