咕咕的计数题 II

题目描述
咕咕最近在学习初等数论,并且对下取整函数产生了极大的兴趣。下取整函数是指一个函数,自变量为 一个实数,因变量为一个整数,这个整数恰好是小于或等于自变量的最大的整数,通常记做 ⌊x⌋。例如, ⌊2.5⌋ = 2,⌊2⌋ = 2,⌊−2.5⌋ = −3。
咕咕发现,给定一个 a,并不是所有的自然数 n 都存在一个正整数 i 使得 ⌊n/i⌋ = a。那么,如果给定 l,r,咕咕好奇在区间 [l,r] 中有多少个正整数能使这个等式有正整数解 i 呢?
那么,聪明的你,你能告诉咕咕吗?
输入
第一行有一个整数 T(1 ≤ T ≤ 1e6),表示数据组数。接下来有 T 行,每行有三个数 a,l,r(1 ≤ a ≤ 1e18,1 ≤ l ≤ r ≤ 1e18),表示一组询问。
输出
输出 T 行,对每组询问,输出一个整数表示答案。
样例输入
4
5 7 10
7 39 42
1000 1000 1000
27 100 1000
样例输出
1
2
1
617
提示
数据范围
当 n = 39,a = 7 时,能找到 i = 5 使得 ⌊39 /5 ⌋ = 7。
题意分析
这道题就是给你一个区间和一个数a,让你求区间内有几个数跟任意数整除之后可以得到a,通过看数据范围可以发现这道题的输入量巨大,所以应该是会可以找到一个规律。并且不能使用cin和cout。
找到的规律AND式子
假定a为7,l为1,r为70,区间内满足条件的值有一下几组

a = 7 ,l = 1 ,r = 70
7
14 15
21 22 23
28 29 30 31
35 36 37 38 39
42 43 44 45 46 47
49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79
80

仔细观察以及在写出来的过程中会发现满足整除出现a的数肯定是在(a*i,a*i+(i-1))内,i=1,2,3……并且一旦超过了a的平方之后,任意一个数都可以整除之后出现a。
规律已经找到了,可是该怎么实现呢,我们会发现,在小于a的平方之前,每次出现的满足条件的数的个数是1,2,3,4,5,6......这样递增的,所以我们让这个数对a整除,对整除出来的数进行从1加到它本身的求和,然后减去有可能不满足的个数,表达不满足的个数,我们看上面的列出来的数,会发现,如果这个数对a取余小于这个数对a整除,就满足条件,所以就可以判断了。写成式子就是

Sum(l/a)-(l%a<l/a?(l/a-l%a):0)
Sum为自定义的从1加到本身的函数,可以直接用一个公式代替,这样方便理解

然后就可以求出左区间以内满足的个数x,右区间以内满足的个数y,y-x就可以求出[x,l)之间的满足条件的个数,但是这种方法并没有对r进行判断,所以我们要再对r进行一次判断,如果r也满足,直接答案加一就行了。
分三种情况考虑

  1. 左区间l大于a的平方,此时所需要输出的答案就是r-l
  2. 左区间l小于a的平方,但右区间r大于a的平方,此时需要把区间分成两段,一段是(a*a,r),一段是(l,a*a-1)。大于a的平方的那一段的区间长度,加上小于a的平方的那一段中满足上面总结的规律的数的个数即答案。
  3. 右区间小于a的平方,此时就可以直接在(l,r)内去找满足条件的数的个数输出就行。

代码实现

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
ll Sum(ll x)
{
    if(x%2==0)  return x/2*(1+x);
    return x*(1+x)/2;
}
int main()
{
    int t;
    ll a,l,r;
    scanf("%d",&t);
    while(t--)
    {
        ll ans=0,x,y;
        scanf("%lld %lld %lld",&a,&l,&r);
        if(sqrt(l)>=a)
        {
            ans=r-l+1;
        }
        else if(sqrt(r)>=a)
        {
            ans=r-a*a+1;
            r=a*a-1;
            x=Sum(l/a)-(l%a<l/a?(l/a-l%a):0);
            y=Sum(r/a)-(r%a<r/a?(r/a-r%a):0);
            if(r%a<r/a)
                y++;
            ans+=y-x;
        }
        else
        {
            x=Sum(l/a)-(l%a<l/a?(l/a-l%a):0);
            y=Sum(r/a)-(r%a<r/a?(r/a-r%a):0);
            if(r%a<r/a)
                y++;
            ans=y-x;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

这里有一个坑,就是分情况讨论的时候l,r跟a的平方比较的时候要对l,r开平方之后跟a比较,第一次我们交的与a的平方比较,WA了,怎么都找不到bug,最后还是机灵的队友说了一下会不会平方之后爆long long,改了一下交了还真过了。。。这数据卡的东西真多。一定要注意!!!