题解
乱搞就能过了。
首先我们考虑如何快速判断C(i, j ) | k 是否成立。
由于$k$非常小， 所以可以对$k$分解质因数， 接着预处理出前N个数的阶乘的因数中 $p_i$ 的个数, 然后就可以$O(1)$判断C(i,j）| k
然后用mk[i][j] 记录 C(i, j) | k ， 并将它转化为二位前缀和， 每次查询只需要输出mk[ n ][ m ]即可
预处理时间复杂度：$O(NlnN + NM)$
每次查询$O(1)$
代码
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rd read() const int N = 2e3 + ; int T, k, n, m;
int pri[], cnt[], tot;
int num[N][], mk[N][N]; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} int fpow(int a, int b) {
int re = ;
for(; b; b >>= , a *= a) if(b & ) re *= a;
return re;
} int jud(int x, int y) {
for(int i = ; i <= tot; ++i) {
int re = ;
re += num[x][i];
re -= num[y][i];
re -= num[x - y][i];
if(re < cnt[i]) return ;
}
return ;
} void init() {
int t = k;
for(int i = ; i <= k; ++i) if(t % i == ) {
pri[++tot] = i;
while(t % i == ) cnt[tot]++, t /= i;
}
for(int j = ; j <= tot; ++j)
for(int l = ; ; ++l) {
int p = fpow(pri[j], l);
if(p >= N) break;
for(int i = ; i < N; ++i) num[i][j] += i / p;
}
for(int i = ; i < N; ++i)
for(int j = ; j <= i; ++j) if(jud(i, j)) mk[i][j] = ;
for(int i = ; i < N; ++i)
for(int j = ; j < N; ++j) mk[i][j] += mk[i - ][j];
for(int i = ; i < N; ++i)
for(int j = ; j < N; ++j) mk[i][j] += mk[i][j - ];
} int main()
{
T = rd; k = rd;
init();
for(; T; T--) {
n = rd; m = rd;
printf("%d\n", mk[n][m]);
}
}