咕咕的计数题 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，改了一下交了还真过了。。。这数据卡的东西真多。一定要注意！！！

赏