题目描述
咕咕最近在学习初等数论,并且对下取整函数产生了极大的兴趣。下取整函数是指一个函数,自变量为 一个实数,因变量为一个整数,这个整数恰好是小于或等于自变量的最大的整数,通常记做 ⌊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也满足,直接答案加一就行了。
分三种情况考虑
- 左区间l大于a的平方,此时所需要输出的答案就是
r-l
。 - 左区间l小于a的平方,但右区间r大于a的平方,此时需要把区间分成两段,一段是(a*a,r),一段是(l,a*a-1)。大于a的平方的那一段的区间长度,加上小于a的平方的那一段中满足上面总结的规律的数的个数即答案。
- 右区间小于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,改了一下交了还真过了。。。这数据卡的东西真多。一定要注意!!!