7-2 整除分块 (15 分)
整除分块，又称数论分块。是数论算法中的重要技巧，你可以在各种需要枚举因子的连续求和类问题中见到它的身影。如杜教筛，莫比乌斯反演化简后的整除分段求和等。 整除分块基于这样一个数学现象：对于任意正整数N，集合
的大小总是严格小于2sqrt（N）。 例如当N=10时S={10,5,3,2,1}，这就使得对于⌊N/i⌋类型的求和类问题，只要快速枚举S集合，就能在sqrt(N) 级别的复杂度内解决问题。
⌊ ⌋符号是向下取整符，⌊x⌋表示不大于x的最大正整数
在学习整除分块这一算法后提出了一个新的问题，对于给定正整数N,x，令S={x:x=⌊ N/i ⌋,i∈1,2,3...N}，时⌊ N/x ⌋在S中是第几大呢（去重降序排序后第几个）？
输入格式:
第一行输入一个正整数T(1≤T≤10 ^6 )，表示测试案例的数目，对于每组案例。 一行两个正整数N,x(1≤x≤N≤10^9 )。
输出格式:
对于每个案例，输出一个正整数，即⌊ N/x ⌋在集合S中降序排第几大。
输入样例:：
2 25 9 1000000000 1000000000
结尾无空行
输出样例:
8 63244
结尾无空行
#include<iostream> #include<cmath> using namespace std; double a[100000000]; int b[100000000]; int main(){ int T,cnt=0,p=0; double n,m,x,y; cin>>T; while(T--){ cin>>n>>x; // cout<<n<<" "<<x<<endl; m=2*sqrt(n); if(m-(int)m)m=(int)m-1; // cout<<m<<endl; for(int i=1;i<=n;i++){ a[i]=n/i; if(a[i]-int(a[i]))a[i]=(int)a[i]; } // cout<<n<<" "<<x<<endl; y=n/x; // cout<<n/x<<endl; if(y-(int)y)y=(int)y; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(a[i]>=a[j]){ int t=a[i]; a[i]=a[j]; a[j]=t; } } } // for(int i=1;i<=n;i++)cout<<a[i]<<" "; // cout<<endl; for(int i=1;i<=n;i++) if(a[i]!=a[i-1]){ // cout<<a[i]<<" "; b[p++]=a[i]; } // cout<<endl; for(int i=1;i<=p;i++){ if(y<=b[i]){ cnt++; } } cout<<cnt<<endl; } return 0; }
