题目描述
组合数表示的是从n个物品中选出m个物品的方案数。举个例子，从（1,2,3) 三个物品中选择两个物品可以有（1,2),(1,3),(2,3)这三种选择方法。根据组合数的定 义，我们可以给出计算组合数的一般公式：
其中n! = 1 × 2 × · · · × n
小葱想知道如果给定n,m和k，对于所有的0 <= i <= n，0 <= j <= min(i,m)有多少对 (i,j)满足是k的倍数。
输入输出格式
输入格式：
第一行有两个整数t,k，其中t代表该测试点总共有多少组测试数据，k的意义见 【问题描述】。
接下来t行每行两个整数n,m，其中n,m的意义见【问题描述】。
输出格式：
t行，每行一个整数代表答案。
输入输出样例
输入样例#1：
1 2 3 3
输出样例#1：
1
输入样例#2：
2 5 4 5 6 7
输出样例#2：
0 7
说明
【样例1说明】
在所有可能的情况中，只有是2的倍数。
【子任务】
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
唯一分解定理~
（在老师×威下写了这篇题解，但真的不是正解啊，只能拿90分……）
先分解k，记录下它的每个质因数以及该质因数的次数~
然后对于每个数，计算它关于k的质因数的次数，如果每个次数都不小于k的次数，那么这个数就是k的倍数~
因为组合数公式c[i][j]=i*(i-1)*(i-2)*...*(i-j+2)*(i-j+1)/(1*2*3*...*(j-1)*j)，所以如果已知c[i][j-1]的所有次数，就可以直接加i-j+1的次数再减去j的次数，顺便判断是否是倍数，如果是，加1即可，最后输出答案~
但这种解法时间复杂度很高，18和20两个点会T的！
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,m,t,k,a[1001][2],tota,num[1001],ans;void chang(int u)
{for(int i=2;i<=u;i++){if(!(u%i)){a[++tota][0]=i;while(!(u%i)) a[tota][1]++,u/=i;}}if(u>1) a[++tota][0]=u,a[tota][1]=1;
}bool findd(int u,int kkz)
{bool flag=1;for(int i=1;i<=tota;i++){while(!(u%a[i][0])) num[i]+=kkz,u/=a[i][0];if(num[i]<a[i][1]) flag=0;}return flag;
}bool find2(int u)
{int kkz=u,flag=1;for(int i=1;i<=tota;i++){num[i]=0;while(!(u%a[i][0])) num[i]++,u/=a[i][0];if(num[i]<a[i][1]) flag=0;}return flag;
}int main()
{
// freopen("problem.in","r",stdin);
// freopen("problem.out","w",stdout);scanf("%d%d",&t,&k);chang(k);while(t--){scanf("%d%d",&n,&m);ans=0;for(int i=1;i<=n;i++){if(find2(i)) ans++;int kkzvu=min(i,m);for(int j=2;j<=kkzvu;j++){findd(i-j+1,1);if(findd(j,-1)) ans++;}}printf("%d\n",ans);}return 0;
}