AcWing:4662. 因数平方和

标签:数论分块 逆元 前缀和

描述

记?f(x)为?x?的所有因数的平方的和。

例如：f(12)=1^2+2^2+3^2+4^2+6^2+12^2。

定义?g(n)=∑i=1nf(i)。

给定?n，求?g(n) 除以?109+7109+7?的余数。

输入格式

输入一行包含一个正整数?n。

输出格式

输出一个整数表示答案?g(n) 除以?109+7109+7?的余数。

数据范围

对于?20% 的评测用例，n≤10^5。
对于?30% 的评测用例，n≤10^7。
对于所有评测用例，1≤n≤10^9。

输入样例：

100000

输出样例：

680584257

?数据范围已经明示了暴力不可取

可以直接利用平方和公式和前缀和来快速求出这一组的平方和。

可以看看大佬的想法,理解怎么写,下面是连接
https://www.acwing.com/solution/content/174106/

以下是AC代码

/* 数论分块+逆元+前缀和 */
#include <bits/stdc++.h>

/* 定义 */
using namespace std;
typedef long long LL;
const int MOD = 1e9 +7;
int n;

/* 快速幂模版 */
int qsm(int a, int b)
{
    int res = 1 % MOD;
    for(; b ; b >>= 1)
    {
        if(b & 1) res = res * 1ll * a % MOD;
        a = a * 1ll * a % MOD;
    }
    return res;
}

/* 求平方和 */
int sum(int x)
{
    return (LL)x * (x + 1) % MOD * (2 * x + 1) % MOD * qsm(6 , MOD - 2) % MOD;
}

int main()
{
    cin >> n;

    /* l ~ r是因子个数相同的一段连续因子 */
    int l = 1 , r , res = 0;
    for(int i = 1; i <= n; i = r + 1)
    {
        int cnt = n / i;
        r = n / cnt;
        /* 负数取模可能是负数,加模再模一下 */
        res = ((res +(LL)cnt * (sum(r) - sum(i - 1))) % MOD + MOD) % MOD;
        
    }
    cout << res;
    return 0;

}