题目类型:
思路
1.求出n的所有因子
2.把所有的因子的2次方相加
3.输出综合
时间复杂度:$O(n)$
正解代码
#include<bits/stdc++.h> //万能头文件
using namespace std;
typedef long long ll;
const int mod=1e9+7; //取模的数
ll n;
ll inv=166666668;
ll qmi(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res=(ll)res*a%mod;
a=(ll)(a*a%mod);
b>>=1;
}
return res;
}
//幂运算
ll sum(ll x)
{
return x*(x+1)%mod*(2*x+1)%mod*inv%mod;
}
int main()
{
cin>>n;
ll ans=0;
inv=qmi(6,mod-2);
for(int l=1;l<=n;l=n/(n/l)+1)
{
int r=n/(n/l),x=n/l;
ans=((ans+x*(sum(r)-sum(l-1)))%mod+mod)%mod;
}
cout<<ans; //输出总和
return 0; //好习惯
}