赛时得分：\(60+67+40+10=177\)
A
记不是 \(i\) 的因子的最小正整数为 \(f(i)\)，给定 \(t\) 组数据，每组一个正整数 \(n\)（\(n \le 10^{18}\)），求 \(\sum_{i=1}^n f(i) \bmod (10^9+7)\)；部分分：30% 数据 \(n \le 100,t=10\)，另外 30% 数据 \(n \le 10^6\)，全数据 \(n \le 10^{18}, t < 10^4\)。（CF 原题：CF1542C Strange Function）
赛时打了一个 \([1,L=10^9]\) 的表发现 \(f(x)\) 的值域很小，然后再发现满足 \(f(i)=x\) 的 \(i\) 个数非常有规律，比如 \(x=2,cnt=L/2,x=3,cnt=L/3\cdots\)，然后思路就卡在这里了，刚好卡在了 CF 题解的 Hint 2 之后就没有进展了。
实际上需要翻译一下 \(f(i)\) 这个函数：钦定 \(f(i)=x\)，则 \(x\) 是非 \(i\) 的因子的最小正整数，那么在 \(x\) 的前面就一定是 \(i\) 的因子（否则就和定义矛盾），所以就有：
记命题 \(p:i \bmod \operatorname{lcm}(1 \sim x-1),q:i \bmod x \ne 0\)
则满足 \(p\) 的 \(i\) 的个数：\(\left\lfloor \dfrac{n}{\operatorname{lcm}(1 \sim x-1)} \right\rfloor\)
则满足 \(p \land \lnot q\) 的 \(i\) 的个数：\(\left\lfloor \dfrac{n}{\operatorname{lcm}(1 \sim x)} \right\rfloor\)
则满足 \(p \land q\) 的个数：\(\left\lfloor \dfrac{n}{\operatorname{lcm}(1 \sim x-1)} \right\rfloor - \left\lfloor \dfrac{n}{\operatorname{lcm}(1 \sim x)} \right\rfloor\)
\(\operatorname{lcm}\) 可直接初始化，要求的式子就转化为：
直接循环求解即可。
https://codeforces.com/problemset/submission/1542/369334177
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e6+7;
constexpr ll mod=1e9+7;
ll l[100]; //lcm(1~i)
inline ll lcm(ull x,ull y)
{return x*y/__gcd(x,y);
}
inline ll solve()
{ll n,ans=0;cin>>n;for(ll x=2;l[x-1]<=n;x++) //钦定f(i)=x {ll contribute=(n/l[x-1]-n/l[x])%mod*x%mod;
// cerr<<' '<<contribute<<endl;ans=(ans+contribute)%mod;}return ans;
}
main()
{
// freopen("math.in","r",stdin);
// freopen("math.out","w",stdout);cin.tie(0)->sync_with_stdio(0);l[1]=1;for(int i=2;i<=42;i++) l[i]=lcm(l[i-1],1ll*i);int T;cin>>T;while(T--) cout<<solve()<<'\n';cout.flush();return 0;
}