我的思路是，枚举每种情况，看看上下约分之后还有没有完整的k，如果有那么ans++

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e3+5;
int t,k,n,m;
long long nk[25][N];
long long ans;
bool is[25]={0,
0,1,1,0,1,
0,1,0,0,0,
1,0,1,0,0,
0,1,0,1,0,
0};//判断某个数是不是质数 
int h[25][25];//h[i][j]表示数i的质因数j在i中的次方 
void yin(){
	for(int i=2;i<=21;i++){//枚举数 
		for(int j=2;j<=k;j++){//枚举i可能的因数 
			if(i%j == 0 && is[j]){//j是质因数 
				int x=i;//x就是当前的数
				while(x >= 1 && x%j == 0){//还能整除 
					h[i][j]++;//质因数数量+1 
					x/=j;
				} 
			}
		}
	}
}
int main(){
	scanf("%d%d",&t,&k);
	for(int kk=1;kk<=k;kk++){
		nk[kk][0]=0;
		nk[kk][1]=0;
	}
	for(int kk=2;kk<=k;kk++){
		for(int i=2;i<=N;i++){//预处理出nk数组 
			int x=i;
			while(x>=1 && (x%kk)==0){//x还能整除以kk 
				nk[kk][i]++;//x中有一个k 
				x/=kk; 
			}
		}
	}
	for(int kk=2;kk<=k;kk++){
		for(int i=2;i<=N;i++){
			nk[kk][i]+=nk[kk][i-1];//逐行前缀和 
		}
	}
	
	yin();//求出因数 
	//cout<<"============"<<endl;
	while(t--){
		ans=0;
		scanf("%d%d",&n,&m);//1,0均不可能是答案，i直接从2开始 
		for(int i=0;i<=n;i++){//枚举 
			for(int j=0;j<=min(i,m);j++){
				if((nk[k][i]-nk[k][j]-nk[k][i-j]) > 0){
					ans++;//这肯定是合法的答案 
				}else{
					if(is[i]){//是质数，没有其他因数 
						continue;//肯定不是答案 
					}
					bool f=1;//标记是否找到答案 
					for(int p=2;p<=k;p++){//找质因数 
						if(h[k][p] &&
						(nk[p][i]-nk[p][j]-nk[p][i-j]) < h[k][p]){
							//是质因数 
							f=0;
							continue;
						}
					}
					if(f){
						ans++;
					}
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}