前言
这题我个人觉得很有意思(可能题做少了),比赛的时候想到了容斥,但是思维上少了转换思考的角度和实现能力所以没做出来,在这里记录一下。
题面
定义函数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,然后根据之前的结论累加即可。
Comments | NOTHING