算法知识点: 前缀和，组合数

复杂度：

解题思路：

首先通过组合恒等式 将所有 模 的余数预处理出来。

然后递推出前缀和：，表示 中 的倍数的个数。

查询时直接查表即可。

C++ 代码： 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 2010;
 
int c[N][N];
int s[N][N];
 
int main()
{
    int T, k;
    scanf("%d%d", &T, &k);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
        {
            if (!j) c[i][j] = 1 % k;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
 
            if (!c[i][j]) s[i][j] = 1;
        }
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            if (i) s[i][j] += s[i - 1][j];
            if (j) s[i][j] += s[i][j - 1];
            if (i && j) s[i][j] -= s[i - 1][j - 1];
        }
 
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
 
        printf("%d\n", s[n][m]);
    }
 
    return 0;
}