BZOJ3930: [CQOI2015]選數(shù)

Description

?我們知道，從區(qū)間[L,H]（L和H為整數(shù)）中選取N個(gè)整數(shù)，總共有(H-L+1)^N種方案。

小z很好奇這樣選出的數(shù)的最大公約數(shù)的規(guī)律，他決定對(duì)每種方案選出的N個(gè)整數(shù)都求一次最大公約數(shù)，以便進(jìn)一步研究。

然而他很快發(fā)現(xiàn)工作量太大了，于是向你尋求幫助。

你的任務(wù)很簡(jiǎn)單，小z會(huì)告訴你一個(gè)整數(shù)K，你需要回答他最大公約數(shù)剛好為K的選取方案有多少個(gè)。

由于方案數(shù)較大，你只需要輸出其除以1000000007的余數(shù)即可。

Input

輸入一行，包含4個(gè)空格分開的正整數(shù)，依次為N，K，L和H。

Output

輸出一個(gè)整數(shù)，為所求方案數(shù)。

Sample Input

2 2 2 4

Sample Output

3

HINT

?樣例解釋

所有可能的選擇方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)
其中最大公約數(shù)等于2的只有3組：(2, 2), (2, 4), (4, 2)
對(duì)于100%的數(shù)據(jù)，1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5 題解Here! 這里寫不了公式，于是寫在這里。

轉(zhuǎn)載于:https://www.cnblogs.com/Yangrui-Blog/p/9033602.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3930: [CQOI2015]选数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。