一、题目
P2424 约数和
二、分析
因为都是加法,那么肯定有的一个性质,即前缀和的思想,就是$$ { ans =\sum_{i=1}^y f(i)} - {\sum_{i=1}^x f(i)} $$
基于上面的性质,分析$ \sum_{i=1}^x f(i) $,因为每个数都是因子之和,那么$1 \to n $ 中一共也就 $n$个因子,其实就将问题转化到了求每个因子的贡献上面。
考虑每个因子最终加 $ \lfloor \frac{n}{i} \rfloor $ 次,所以最终$$ { ans = \sum_{i=1}^y i \lfloor \frac{y}{i} \rfloor} - {\sum_{i=1}^x \lfloor \frac{x}{i} \rfloor} $$
然后结合整除分块求解即可。
三、AC代码
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 typedef long long ll;
5
6 ll solve(ll n)
7 {
8 ll ans = 0;
9 ll L, R;
10 for(L = 1; L <= n; L = R + 1)
11 {
12 ll res = n/L;
13 if(res)
14 {
15 R = n/res;
16 }
17 else
18 R = n;
19 ans += res * (R - L + 1) * (R + L) / 2;
20 }
21 return ans;
22 }
23
24 int main()
25 {
26 //freopen("input.txt", "r", stdin);
27 ll x, y;
28 while(scanf("%lld%lld", &x, &y) != EOF)
29 {
30 printf("%lld\n", solve(y) - solve(x - 1));
31 }
32 return 0;
33 }
转载于:https://www.cnblogs.com/dybala21/p/11233273.html