P2261 [CQOI2007]余数求和 【整除分块】

一、题面

  P2261 [CQOI2007]余数求和

二、分析

  参考文章:click here

  对于整除分块,最重要的是弄清楚怎样求的分得的每个块的范围。

  假设$ n = 10 ,k = 5 $  

$$   i : 1 \  2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10  \\  \lfloor \frac{k}{i} \rfloor :  5 \ 2 \ 1 \ 1 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0   $$

  我们推导出假设$ L = i $,那么,对应的 $ \lfloor \frac{k}{i} \rfloor $ 相等的最右边界为 $  R =  \lfloor \frac{k}{  \lfloor \frac{k}{i} \rfloor } \rfloor $.(具体证明可以看参考文章。)

  需要注意的细节是

  1 $R$可能超过$n$,所以要限制一下。

  2 一定要用$long long$。

三、AC代码

 1 #include <bits/stdc++.h>
2
3 using namespace std;
4 typedef long long ll;
5
6 int main()
7 {
8 //freopen("input.txt", "r", stdin);
9 ll n, k;
10 while(scanf("%lld%lld", &n, &k) != EOF)
11 {
12 ll ans = n * k;
13 ll L, R;
14 for(L = 1; L <= n; L = R + 1)
15 {
16 ll res = k/L;
17 if(res)
18 {
19 // 必须加min,因为k/res可能超过n,例如 k = 10, n = 6
20 R = min(k/res, n);
21 }
22 else
23 R = n;
24 ans -= res * (R - L + 1) * (R + L) / 2;
25 }
26 printf("%lld\n", ans);
27 }
28 return 0;
29 }
上一篇:JavaWeb-11Listener监听器、JDBC-接口、PreparedStatement对象


下一篇:kernel中文件的读写操作可以使用vfs_read()和vfs_write