牛客寒假训练营第二场D题
Description：
整除分块，又称数论分块。是数论算法中的重要技巧，你可以在各种需要枚举因子的连续求和类问题中见到它的身影。如杜教筛，莫比乌斯反演化简后的整除分段求和等。balabala
...(复制过来乱码，遂放弃)，题目链接：https://ac.nowcoder.com/acm/contest/9982/D
题意就是(S = {lfloor dfrac{N}{i} floor})，其中(iin[1, N])，输入T，N，x。T表示测试的个数，求每个测试(lfloor dfrac{N}{x} floor)在去重集合S中降序排序第几大。
示例输入
2 // 测试的个数
25 9
1000000000 1000000000
示例输出
8
63244
说明
当n=25时候,(S={25,12,8,6,5,4,3,2,1}) (lfloor dfrac{25}{9} floor=2)，2在S集合中是降序排列的第8个，所以输出8
Solution：
1、首先了解一下整除分块的性质，对于一个正整数N
1、(lfloor dfrac{N}{i} floor)最多有(2sqrt{N})种
证明：
- 当(i le sqrt{N})， 一共有(sqrt{N})种
- 当(i > sqrt{N}) ， (dfrac{N}{i} <= sqrt{N})， 最多有(sqrt{N})种；因为有可能对于所有的(i > sqrt{n})，(dfrac{N}{i} < sqrt{N})，那么此时只有(sqrt{N} - 1)种
根据这个题目别人的代码我可以知道：当(lfloor sqrt{N} floor = lfloor dfrac{N}{sqrt{N}} floor)时，有(2sqrt{N} - 1)种（不知道如何证明暂时）
2、(b = lfloor dfrac{N}{a} floor) 时， (a = lfloor dfrac{N}{b} floor)
这个类似于实数除法中除数和商的互逆性质：$b = dfrac{N}{a} $ 时， (a = dfrac{N}{b})
不知如何证明
3、对于(lfloor dfrac{N}{j} floor) 与(lfloor dfrac{N}{i} floor)相等时，j最大的取值是(lfloor dfrac{N}{lfloor dfrac{N}{i} floor} floor)
也就是说(forall j in [i, lfloor dfrac{N}{lfloor dfrac{N}{i} floor} floor])， (lfloor dfrac{N}{j} floor = lfloor dfrac{N}{i} floor)
证明看这个哥哥的：https://www.cnblogs.com/0xfffe/p/9648943.html
2、本题解法
#include<bits/stdc++.h>
using namespace std;
int T, N, x;
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d %d", &N, &x);
int sq = sqrt(N);
int tmp = N/x;
int tot;
// 求出S中集合元素个数（即有多少种数字）
if(sq==N/sq) tot = 2*sq-1;
else tot = 2*sq;
// 如果 x >= sqrt(n)
if(x>=sq) printf("%d
",tot-tmp+1);
// else
else printf("%d
",x); // N/x < sqrt(n)
}
return 0;
}
这里主要用到了性质1和2，
比如对于N=25，(S={25,12,8,6,5,4,3,2,1})
- x = 2时，25/2 = 12，ans = 2；也就是说ans = x，这是因为x 和 anx/x 在S中是关于(sqrt{N})对称的
- x = 10时，25/10 = 2， ans = |S| - 2+1 = 8； 即ans = |S| - N/x + 1
对于另一个类似的题目，主要用到性质3
求(sum_{i=1}^{N} lfloor dfrac{N}{i} floor)
// 求和模板
#define long long ll
void summ(ll N)
{
ll ans;
for(ll l=1, r; l<=n; l=r+1){
r = n/(n/i); // 区间右端点
ans += (r-l+1)*(n/i); // [l,r]区间内部的都是n/i
}
return ans;
}
参考
https://www.limstash.com/articles/201901/1206