思路分析
题目中要求的就是下面图示左边的累加式
平方和公式 1^2 + 2^2 + ... + n^2 = n * (n + 1) * (n * 2 + 1) / 6
i为每一段的起点,如何找终点,只需要找最大的y满足y = n /x
y = n / x 证明可以看第137场周赛————最多的布丁题解
https://www.acwing.com/solution/content/220910/
代码实现
__int128做法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL cal(int n)
{
//三个1e9相乘会爆long long
return n * (__int128)(n + 1) * (n * 2 + 1) / 6 % mod;
}
int main()
{
int n;
cin >> n;
LL res = 0;
for(int i = 1; i <= n;)
{
int x = n / i, y = n / x;
res = (res + (cal(y) - cal(i - 1)) * x) % mod;
i = y + 1;
}
//res可能为负数,所以要通过加上模数变为正
cout << (res + mod) % mod << endl;
return 0;
}
求逆元做法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL qmi(int a, int b, int k) //快速幂求逆元
{
LL res = 1;
while(b)
{
if(b & 1) res = (LL)res * a % k;
b >>= 1;
a = (LL)a * a % k;
}
return res;
}
LL cal(int n)
{
//这里n * (n + 1)会爆int所以1要写为1ll
return n * (n + 1ll) % mod * (n * 2 + 1) % mod * qmi(6, mod - 2, mod) % mod;
}
int main()
{
int n;
cin >> n;
LL res = 0;
for(int i = 1; i <= n;)
{
int x = n / i, y = n / x;
res = (res + (cal(y) - cal(i - 1)) * x) % mod;
i = y + 1;
}
cout << (res + mod) % mod << endl;
return 0;
}