这题还可以用线筛快速分解$n!$质因子来做啊，为什么没有人想到呢？起码题解里面没有

本人代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define maxn 5005
#define rep(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;

inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}

void write(int x) {
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

int vis[maxn],cnt,pri[maxn],tot[maxn][maxn],k,n,m,ans[maxn][maxn],p[maxn],c[maxn];

void pretreat() {
	vis[1]=1;
	rep(i,2,2000) {
		if(!vis[i]) {
			pri[++cnt]=i;
			rep(j,1,2000) for(register int t=i;t<=j;t*=i)
			tot[j][i]+=j/t;
		}
		for(register int j=1;j<=cnt&&pri[j]*i<=2000;j++) {
			vis[pri[j]*i]=1;
			if(!(i%pri[j])) break;
		}
	}
	cnt=0;
	for(int i=2;i*i<=k;i++) {
		if(!(k%i)) {
			p[++cnt]=i;
			while(!(k%i)) k/=i,c[cnt]++;
		}
	}
	if(k>1) p[++cnt]=k,c[cnt]++;
	rep(i,0,2000) {
		rep(j,0,i) {
			int flag=0;
			rep(l,1,cnt) {
				if(tot[i][p[l]]-tot[j][p[l]]-tot[i-j][p[l]]<c[l]) {
					flag=1;
					break;
				}
			}
			if(!flag) ans[i][j]++;
			if(j-1>=0) ans[i][j]+=ans[i][j-1];
		}
	}
}

int main() {
	int T=read();
	k=read();
	pretreat();
	rep(I,1,T) {
		n=read(),m=read();
		int res=0;
		rep(i,1,n) res+=ans[i][min(i,m)];
		write(res),putchar('\n');
	}
	return 0;
}

但是代码确实很长