前言
emm.....考场其实想到T2正解的思路了，但是不会优化，导致有些拉胯少了50分。还有就是说数学题我是真不行，向上次 \(fengwu\) 的筛我不会，这会最简单的容斥想这么老半天学这么老半天都不会，着实是有些废物了。
T1 十年之约
一道很简单的数学题QAQ，但我就是不会，我真服了。
首先对于 \(f(i)=k\)，则我们的 \(i\) 一定能被 \(1,2,...,k-1\) 的所有数整除并且一定不能被 \(k\) 整除，于是就有了我们下面的式子：\(lcm(1,2,3,...,k-1) \mid i\) 且 \(k \nmid i\)。
对于一个集合里面任意的数 \(i\) 在满足 \(lcm(1,2,3,...,k-1) \mid i\) 的情况下它只会有两种情况，能被 \(k\) 整除和不能被 \(k\) 整除。所以用一个小小的容斥就能求出来题目要求的 \(k\) 的个数啦 \(k\) ：\(\left\lfloor \frac{i}{lcm(1,2,3,...,k-1)} \right\rfloor - \left\lfloor \frac{i}{lcm(1,2,3,...,k)} \right\rfloor\)。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll t, n;
inline void solve() {
ll lcm = 1, last, ans = 0;
for (ll i = 2; lcm <= n; ++ i) {
last = lcm;
lcm = lcm * i / __gcd(lcm, i);
ans = (ans + i * (n / last - n / lcm) % mod + mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
scanf("%lld", &t);
while (t --) {
scanf("%lld", &n);
solve();
}
return 0;
}