蓝桥杯2018年第九届真题-矩阵求和-题解（C++代码）

解题思路:

数论函数(分块)+线性筛+推柿子

本题其实可以加多组测试数据目前复杂度是√n  

公式如下

注意事项:

参考代码:

#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e7+10;
ll mu[N];
int pri[N],num;
bool st[N];
void init_pri(ll n){
mu[1]=1;
st[1]=true;
for(int i=2;i<=n;++i){
if(!st[i]){
pri[++num]=i;
mu[i]=((1ll*i*i-1)%mod+mod)%mod;
}
for(int j=1;i*pri[j]<=n;++j){
st[i*pri[j]]=true;
if(i%pri[j]==0){
mu[i*pri[j]]=1ll*mu[i]*pri[j]%mod*pri[j]%mod;
break;
}
mu[i*pri[j]]=((1ll*mu[i]*mu[pri[j]])%mod+mod)%mod;
}
}
for(int i=1;i<=n;++i){
mu[i]=((mu[i]+mu[i-1])%mod+mod)%mod;
}
}
ll calc(ll n){
ll l=1,r;
ll ans=0;
for(;l<=n;l=r+1){
r=n/(n/l);
ans=(ans+1ll*(mu[r]-mu[l-1])%mod*(n/l)%mod*(n/l)%mod)%mod;
if(ans<0)ans+=mod;
}
return ans;
} 
int main()
{
ll n;
cin>>n;
init_pri(n);
cout<<calc(n)<<endl;
}