一伯分代码和思路

刚看到这个题，想到的就是i从1到n遍历，每个i出现做为因子的个数是（n/i），全部加起来就可以了

    代码：

const LL mod=1000000007;
LL ans=0;

int main(){
    LL n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ans+=(((n/i)*i)%mod)*i;
        ans%=mod;
    }
    cout<<ans;
}

这个时间复杂度是10^9，并且循环体里还有除法，必然是过不了的，只有30分

但是有了这个思路，我们就想到是否可以利用公式

1^2+2^2+...+n^2=n*(n+1)*(2*n+1)/6

进行优化呢？（蓝桥杯似乎很喜欢出这种公式的使用，三次方相加公式好像也出过）

利用这个公式，很容易写出这样的代码

const LL mod=1000000007;
const LL am=1000000007LL*6;    //下边有解释
LL ans=0;

int main(){
    LL n;
    cin>>n;
    LL m=n;
    for(int i=1;i<=n;i++){
        m=(n/i);                                //每次计算1~m
        LL temp=(((m*(m+1))%am)*(2*m+1))%am;    //计算1加到m的公式
        temp/=6;
        ans+=temp;
        ans%=mod;
    }
    cout<<ans;
}

因为这个公式有除以6，所以需要进行求逆元计算。有的小伙伴可能不太清楚求逆元是干什么的，简单解释一下就是，我们要计算（b/a）%m，是没办法直接（（b%m）/(a%m)）的，如果b是几个大数相乘，就没办法直接乘的时候取模，这时候就需要用到逆元了，我们只要求出a在m下的逆元x，则(b*x)%m＝（b/a）%m，就可以计算了！逆元可以用扩展欧几里得或者快速幂计算。而这里的am是我《算法笔记》学来的，计算（b/a）%m不用求逆元，直接（b%(a*m)）/a就可以得出答案（大家先别急着学这个公式，先把求逆元学会）

但是从这里我们可以看到，复杂度仍然是10^9，不过有了这两个思路，我们可以对(n/10000)以上的数字利用公式计算，然后对1~(n/10000)用第一种思路计算，这样时间复杂度就降到了10^5

#include using namespace std;

typedef long long LL;

const LL mod=1000000007;
const LL am=1000000007LL*6;
LL ans=0;

int main(){
    LL n;
    cin>>n;
    LL m=n;
    for(int i=1;i<=10000;i++){
        m=(n/i);
        if(m==0){        //对n小于10000的情况进行处理
            cout<<ans;
            return 0;
        }
        LL temp=(((m*(m+1))%am)*(2*m+1))%am;
        temp/=6;
        ans+=temp;
        ans%=mod;
    }
    for(int i=1;i<=m;i++){
        ans+=(((n/i-10000)*i)%mod)*i;
        ans%=mod;
    }
    cout<<ans;
}

但是这个代码只得了90分，这就是贪图便宜的错，（b%(a*m)）/a虽然写的快，但会被一些莫名的数据卡住，所以还是要先求出逆元，再计算，下面的是一伯分代码

#include using namespace std;

typedef long long LL;

const LL mod=1000000007;
const LL ni=166666668;
LL ans=0;


int main(){
    LL n;
    cin>>n;
    LL m=n;
    for(int i=1;i<=10000;i++){
        m=(n/i);
        if(m==0){
            cout<<ans;
            return 0;
        }
        LL temp=(((m*(m+1))%mod)*(2*m+1))%mod;
        temp*=ni;
        temp%=mod;
        ans+=temp;
        ans%=mod;
    }
    for(int i=1;i<=m;i++){
        ans+=(((n/i-10000)*i)%mod)*i;
        ans%=mod;
    }
    cout<<ans;
}