咕咕的计数题 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代码实现

#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,改了一下交了还真过了。。。这数据卡的东西真多。一定要注意!!!