一、題目
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