Description

粗题⼈症重承诺此题不考你没学过的算法

给你⼀个区间[L,R]

需要选择N个数，这N个数都在这个区间范围内

那么我们知道⼀共有[R-L+1]^N种选法

假如我们想要这N个数的最⼤公约数恰好是K

请问⼀共有多少种选法，输出答案对1e9+7取模

Input

 多组测试数据 对于每组数据，输⼊⼀⾏包含4个整数N,K,L,R(1<=N,K,L<=10^9,L<=R<=10^9)

(0<=R-L<=10^5)

Output

 对于每组数据输出⼀个整数

Sample Input

2 2 2 4
2 100 2 4
1 5 5 5
73824 17347 9293482 9313482
222 222 222 22222

Sample Output

3
0
1
0
339886855

HINT

#include <iostream> 
#include <fstream> 
#include <sstream> 
#include <cstdio> 
#include <cstring> 
#include <cstdlib> 
#include <cmath> 
#include <ctime> 
#include <algorithm> 
#include <vector> 
#include <queue> 
#include <deque> 
#include <stack> 
#include <set> 
#include <map> 
#include <complex> 
#include <bitset> 
#include <iomanip> 
#include <utility> 

using namespace std; 

typedef long long LL; 
typedef pair<int,int> pii; 
typedef complex<double> point; 

const int mod = 1000000007; 

int f[200000]; 

int POW (int base, int p){ 
  int ret = 1, cur = base; 
  while (p){ 
    if (p & 1) ret = (LL)ret * cur % mod; 
    p>>=1; 
    cur = (LL)cur * cur % mod; 
  } 
  return ret; 
} 

struct RandomGCD{ 
  int countTuples(int N, int K, int lo, int hi){ 
      memset(f, 0, sizeof(f));
    lo = (lo+K-1)/K, hi = hi/K;  
    if (lo > hi) 
      return 0; 
    for (int i=100000; i>=1; i--){ 
      int L = (lo + i-1) / i; 
      int H = hi / i; 
      if (L <= H){ 
        f[i] = POW(H-L+1, N);  
        f[i]-= (H-L+1); 
        if (f[i] < 0) f[i]+= mod; 
        for (int j=i*2; j<=100000; j+=i){ 
          f[i]-=f[j]; 
          if (f[i]<0) f[i]+= mod; 
        } 
      } 
    } 
    if (lo == 1) 
      f[1] = (f[1] + 1) % mod; 
    return f[1]; 
  }   
};

int main() {
    RandomGCD test;
    int N, K, L, R;
    while (cin >> N >> K >> L >> R) {
        cout << test.countTuples(N, K, L, R) << endl;
    }
    return 0;
}