题意: \(f(i)=x\),\(x\)为最小的不能整除\(i\)的数.求\(\sum^{n}_{i=1}f(i)\ mod\ 10^9+7\).

题解:首先,\(1,2,...,x-1|i\),即\(i\)一定是\(lcm(1,2,...,x-1)\)的倍数,我们现在来看\(f(i)\)的值,当\(f(i)=2\)时,\(i\)的最小值是\(1\),\(f(i)=3\)时,\(i\)的最小值是\(2\),\(f(i)=4\)时,\(i\)的最小值是\(6\),因为\(lcm(1,2,3)=6\).以此类推,最后发现\(f(i)=43\)时,\(i\ge10^{16}\).因为\(f(i)\)最小为\(2\),所以\(ans\)初始化为\(2*n\).然后接下来我们要计算答案,可以从小到大线性枚举\(f(i)\)的值,比如说\(f(i)=4\),最小的\(i\)为\(6\),那么对于所有的\(i=k*6\),它都包含\((1,2,3)\),所以当前这个因子可以选,答案因子还在后面(因为线性,所以+1),那么当前贡献就要+1,即\(ans+=n/lcm(1,2,3)\).以此类推即可得到答案.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}


int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		ll n;
		cin>>n;
		ll ans=n*2;
		ll cur=1;
		for(int i=3;i<=43;++i){
			cur=lcm(cur,i-1);
			ans=(ans+n/cur)%mod;
		}
		cout<<ans<<'\n';	
	}
	
    return 0;
}