题目描述
blablabla
样例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
LL calc(int n)
{
return n * (__int128)(n + 1) * (n * 2 + 1) / 6 % MOD;
}
int main()
{
int n;
cin >> n;
int res = 0;
for (int i = 1; i <= n;)
{
int x = n / i, y = n / x;
res = (res + (calc(y) - calc(i - 1)) * x) % MOD;
i = y + 1;
}
cout << (res + MOD) % MOD << endl;
return 0;
}
求逆元的写法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
LL calc(int n)
{
return n * (n + 1ll) % MOD * (n * 2 + 1) % MOD * 166666668 % MOD;
}
int main()
{
int n;
cin >> n;
int res = 0;
for (int i = 1; i <= n;)
{
int x = n / i, y = n / x;
res = (res + (calc(y) - calc(i - 1)) * x) % MOD;
i = y + 1;
}
cout << (res + MOD) % MOD << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla