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; }

?

總結

以上是生活随笔為你收集整理的粗题⼈不考你没学过的算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。