思路
如果用试除法求约数暴力求解只能过20%的数据
c++代码O(n^3/2)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
LL n,res;
LL f(LL x)
{
LL ans = 0;
for(LL i = 1;i <= x / i;i++)
if(x % i == 0)
{
ans = (ans + i * i) % mod;
if(i * i == x) continue;
LL j = x / i;
ans = (ans + j * j) % mod;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(LL i = 1;i <= n;i++)
res = (res + f(i)) % mod;
cout << res << endl;
return 0;
}
考虑找数学规律,没找到,ok,g了,看大佬题解,发现对于每一个因数i,有n / i个i的倍数,其中每个倍数对应于i的贡献值为i * i,而1 ~ n都可以作为因数i,最后对每个i进行处理然后求和即可
涉及知识
1.整数分块
例如10 / i,i从1枚举到10,得到10,5,3,2,2,1,1,1,1,1,其中相等的数字为一块,那么便要寻找每一块的左右端点,通过y总的推导可知左右端点分别为i和n / (n / i),对左右端点维护的数字区间求平方和即可
2.快速幂求逆元
对区间求平方和时所用公式为n * (n + 1) * (n + n + 1) / 6,达到了恐怖的1e27会爆long long,但是最终结果要求对mod=1e9+1取模,故可以在这一步先取模,因为(a + b) % p == (a % p + b % p) % p,但是涉及到 / 6,除法是不满足这个定理的,故可以考虑乘以6的逆元与之等效
AC的c++代码O(n^1 / 2)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL s(int n)
{
return (LL)n % mod * (n + 1) % mod * (n + n + 1) % mod * 166666668 % mod;
}
int n;
int main()
{
cin >> n;
/*
int k = mod - 2,a = 6;
int res = 1 % mod;
while(k)
{
if(k & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
k >>= 1;
}
cout << res << endl;
//快速幂求逆元
*/
int ans = 0;
for(int i = 1;i <= n;)
{
int x = n / i,y = n / x;
ans = (ans + (s(y) - s(i - 1)) * x) % mod;
i = y + 1;
}
cout << (ans + mod) % mod << endl;
return 0;
}