Problem Description
In mathematics, the function d(n) denotes the number of divisors of positive integer n.
For example, d(12)=6 because 1,2,3,4,6,12 are all 12's divisors.
In this problem, given l,r and k, your task is to calculate the following thing :
image.png
Input
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).
Output
For each test case, print a single line containing an integer, denoting the answer.
Sample Input
3
1 5 1
1 10 2
1 100 3
Sample Output
10
48
2302
这个题我觉得还是有必要写个题解的
比赛的时候想了很久，但是脑子发轴，想出来的时候，比赛还有半个小时，当时大的方向虽然想清楚了，小的方面还有点没弄好，所以最后没有AC。唉，难受。
我一步一步来说一下这个题的思路吧。
image.png
首先，看到这个公式有什么想法嘛；
d(n) 是指n这个数包含的因子数
一个数所包含的因子数该怎么计算呢？
比如12
它的质因子是3和2，并且3的个数为1，2的个数为2
那么根据排列组合的原理，在3这个因子上有2中取法，取0或1。在2这个因子有三种取法0，1，2。
那么根据乘法原则12的总因子数应该为23 = 6。
那么d(n^k)呢？
k相当于这个数的质因子个数变成了原来的k倍。
所以d(12^k) = (k+1) * (2k+1)；
所以至此可以可出一个结论，一个数n的d(n)等于它的质因子Pi的次方bi乘k加1；
如果 n = P1^b1 + P2^b2 + P3^b3 …… + Pn^bn；
那么d(n) = (b1k+1) * (b2k+1) * (b3k+1) ……(bnk+1)；
那么我们已经解决了怎么算的问题啦。
如果给我足够的时间这时候我已经可以算出来啦！
但是可惜题目给的时间限制是5000ms，而
image.png
所以，拉闸，想办法优化吧
题目给的数据范围是到10^12这个数量级的
我们知道一个任意一个数字都是由他的质因子组成的，质数是构成数字的基本元素。
所以1012这个数量级的合数肯定是由sqrt(1012) = 106这个数量级内的质数构成的。这个结论很好理解吧。合数必定由两个及两个以上的质因子构成。而构成它的质因子中最大的都绝对不会超过106；
max(pi) <10^6
那么我们解决了区间内所有合数的问题；
质数呢？质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为质数。
如果n是一个质数，那么d(n) = K+1。
所以我们完全可以用筛法，把给定区间内所有的合数的d(n)值求出来，没有算到的那肯定就是质数了，质数的话就乘（k+1） 。
我们可以开一个数字组R[]保存这个区间内的数字，然后计算这个数字包含的质因子Pi的个数bi时，让这个数字除去Pi^bi，num[i]=(bi*k+1)。
那要是R[i]没变的那肯定就是没筛到的质数；
然后把每个num[i]的值加起来就可以啦。
网友评论