39 lines
768 B
C++
39 lines
768 B
C++
// lanqiao 3075 特殊的多边形
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e5+9;
|
|
int n, cnt[N], prefix[N];
|
|
|
|
void dfs(int dep, int st, int mul, int sum){
|
|
// 剪枝1
|
|
if(mul > 1e5) return;
|
|
if(dep == n + 1){
|
|
cnt[mul]++;
|
|
return;
|
|
}
|
|
// 剪枝2
|
|
int up = pow(1e5 / mul, 1.0/(n - dep + 1)) + 3;
|
|
for(int i = st + 1; i < (dep == n?min(sum, up):up); i++){
|
|
dfs(dep+1, i, mul * i, sum + i);
|
|
}
|
|
}
|
|
|
|
int main(){
|
|
int q; cin >> q >> n;
|
|
dfs(1, 0, 1, 0);
|
|
for(int i = 1; i <= 1e5; i++){
|
|
prefix[i] = prefix[i-1] + cnt[i];
|
|
}
|
|
while(q--){
|
|
int l, r; cin >> l >> r;
|
|
cout << prefix[r] - prefix[l-1] << '\n';
|
|
}
|
|
return 0;
|
|
}
|
|
/* test samples
|
|
4 3
|
|
1 10
|
|
30 50
|
|
60 200
|
|
200 400
|
|
*/ |