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 :
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
這個(gè)題我覺得還是有必要寫個(gè)題解的
比賽的時(shí)候想了很久，但是腦子發(fā)軸，想出來的時(shí)候份帐，比賽還有半個(gè)小時(shí)垦藏，當(dāng)時(shí)大的方向雖然想清楚了随珠，小的方面還有點(diǎn)沒弄好补疑，所以最后沒有AC瘦馍。唉欣喧，難受腌零。
我一步一步來說一下這個(gè)題的思路吧。
首先唆阿，看到這個(gè)公式有什么想法嘛益涧；
d(n) 是指n這個(gè)數(shù)包含的因子數(shù)
一個(gè)數(shù)所包含的因子數(shù)該怎么計(jì)算呢？
比如12
它的質(zhì)因子是3和2驯鳖，并且3的個(gè)數(shù)為1闲询，2的個(gè)數(shù)為2
那么根據(jù)排列組合的原理，在3這個(gè)因子上有2中取法臼隔，取0或1嘹裂。在2這個(gè)因子有三種取法0，1摔握，2寄狼。
那么根據(jù)乘法原則12的總因子數(shù)應(yīng)該為23 = 6。
那么d(n^k)呢？
k相當(dāng)于這個(gè)數(shù)的質(zhì)因子個(gè)數(shù)變成了原來的k倍泊愧。
所以d(12^k) = (k+1) * (2k+1)伊磺；
所以至此可以可出一個(gè)結(jié)論，一個(gè)數(shù)n的d(n)等于它的質(zhì)因子Pi的次方bi乘k加1删咱；
如果 n = P1^b1 + P2^b2 + P3^b3 …… + Pn^bn屑埋；
那么d(n) = (b1k+1) * (b2k+1) * (b3k+1) ……(bnk+1)；
那么我們已經(jīng)解決了怎么算的問題啦痰滋。
如果給我足夠的時(shí)間這時(shí)候我已經(jīng)可以算出來啦摘能！
但是可惜題目給的時(shí)間限制是5000ms，而
所以敲街，拉閘团搞，想辦法優(yōu)化吧
題目給的數(shù)據(jù)范圍是到10^12這個(gè)數(shù)量級(jí)的
我們知道一個(gè)任意一個(gè)數(shù)字都是由他的質(zhì)因子組成的，質(zhì)數(shù)是構(gòu)成數(shù)字的基本元素多艇。
所以1012這個(gè)數(shù)量級(jí)的合數(shù)肯定是由sqrt(1012) = 106這個(gè)數(shù)量級(jí)內(nèi)的質(zhì)數(shù)構(gòu)成的逻恐。這個(gè)結(jié)論很好理解吧。合數(shù)必定由兩個(gè)及兩個(gè)以上的質(zhì)因子構(gòu)成峻黍。而構(gòu)成它的質(zhì)因子中最大的都絕對(duì)不會(huì)超過106复隆；
max(pi) <10^6
那么我們解決了區(qū)間內(nèi)所有合數(shù)的問題；
質(zhì)數(shù)呢姆涩？質(zhì)數(shù)定義為在大于1的自然數(shù)中挽拂，除了1和它本身以外不再有其他因數(shù)，這樣的數(shù)稱為質(zhì)數(shù)阵面。
如果n是一個(gè)質(zhì)數(shù)轻局，那么d(n) = K+1洪鸭。
所以我們完全可以用篩法样刷，把給定區(qū)間內(nèi)所有的合數(shù)的d(n)值求出來，沒有算到的那肯定就是質(zhì)數(shù)了览爵，質(zhì)數(shù)的話就乘（k+1） 置鼻。
我們可以開一個(gè)數(shù)字組R[]保存這個(gè)區(qū)間內(nèi)的數(shù)字，然后計(jì)算這個(gè)數(shù)字包含的質(zhì)因子Pi的個(gè)數(shù)bi時(shí)蜓竹，讓這個(gè)數(shù)字除去Pi^bi箕母，num[i]=(bi*k+1)。
那要是R[i]沒變的那肯定就是沒篩到的質(zhì)數(shù)俱济；
然后把每個(gè)num[i]的值加起來就可以啦嘶是。
