前言

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;
}