Nowcoder9982D.牛牛与整除分块（财富密码）

链接：https://ac.nowcoder.com/acm/contest/9982/D
来源：牛客网

题目描述

整除分块，又称数论分块。是数论算法中的重要技巧，你可以在各种需要枚举因子的连续求和类问题中见到它的身影。如杜教筛，莫比乌斯反演化简后的整除分段求和等。
整除分块基于这样一个数学现象：对于任意正整数N，集合S={x:x=⌊Ni⌋,i∈1,2,3...N}S=left { x:x=left lfloor frac{N}{i} ight floor ,iin 1,2,3...N ight }S={x:x=⌊iN​⌋,i∈1,2,3...N}的大小总是严格小于2N2 sqrt N2N​。

例如当N=10时S={10,5,3,2,1}，这就使得对于⌊Ni⌋left lfloor frac{N}{i} ight floor⌊iN​⌋类型的求和类问题，只要快速枚举S集合，就能在Nsqrt NN​级别的复杂度内解决问题。

⌊    ⌋left lfloor ; ; ight floor⌊⌋符号是向下取整符，⌊x⌋left lfloor x ight floor⌊x⌋表示不大于x的最大正整数

牛牛在学习整除分块这一算法后提出了一个新的问题，对于给定正整数N,x，令S={x:x=⌊Ni⌋,i∈1,2,3...N}S=left { x:x=left lfloor frac{N}{i} ight floor ,iin 1,2,3...N ight }S={x:x=⌊iN​⌋,i∈1,2,3...N}，时⌊Nx⌋left lfloor frac{N}{x} ight floor⌊xN​⌋在S中是第几大呢（去重降序排序后第几个）？

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+100;
int main () {
    int t,n,x;
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&x);
        long long ans=0;
        int tt=sqrt(n);
        int y=tt*2;
        if (tt*(tt+1)>n) y--;
        //printf("%d
",tt);
        if (x>tt)
            ans=y-n/(x)+1;
        else
            ans=x; 
        printf("%lld
",ans);
    }
}