前言

这题我个人觉得很有意思（可能题做少了），比赛的时候想到了容斥，但是思维上少了转换思考的角度和实现能力所以没做出来，在这里记录一下。

题面

定义函数f(i)=最小的正数x使得x不是i的因子，求\sum\limits_{i=1}^{n}f(i)\bmod{10^9+7}。

思路

考虑f(i)=x的这样的f(i)的个数。
{f(i)=x}\Leftrightarrow{f(i)\mid{\operatorname{lcm}(1,2,\cdots,x-1)}\wedge{f(i)}\nmid{\operatorname{lcm}(1,2,\cdots,x)}}

实现

#include<iostream>
using namespace std;
using ll=long long;
const int mod=1e9+7;
ll lcm[100];
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    lcm[0]=lcm[1]=1;
    for(int i=2;i<=50;i++){
        lcm[i]=lcm[i-1]*i/gcd(lcm[i-1],i);
        if(lcm[i]>1e16)break;
    }
    int t;
    cin>>t;
    while(t--){
        ll n,ans=0;
        cin>>n;
        for(ll i=1;lcm[i-1]<=n;i++){
            ans=(ans+n/lcm[i-1])%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

细节

代码中先是用前缀lcm处理出足够的lcm，然后根据之前的结论累加即可。