题目描述
组合数表示的是从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的倍数。
【子任务】
//这个方法比较简单
//由组合数可知，c(m,n)=(n-m+1)!/(m!) ,那么要想组合数能整除k，就必须统计k的质因数 是否包涵与c的质因数。
// 用g[i]表示i中k的质因数个数
// 用f[i]表示i!中k的质因数个数
//因为2-21 中k能分解成两种不同的质因数，所以有g2,f2
//用 z[i][j]代表 c(1到j,i)中能被k整除的个数
//用 u[i][j]代表 c(1到j,1到i)中能被k整除的个数 #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string.h>
using namespace std;
int read() //读入优化
{
int in=,k=;char c=getchar();
for(;c>''||c<'';c=getchar()) if(c=='-') k=-;
for(;c<=''&&c>='';c=getchar())
in=in*+c-'';
return k*in;
}
int k,k2,nk,nk2,n,m,all,g[],g2[],jy[][]; int a[],f[],f2[],t,qu[][],maxn=; bool check(int n,int m) //判断组合数 C(m,n) 是否能被k整除
{
int a=f[n]-f[n-m+-];
int b=f[m];
int c=f2[n]-f2[n-m+-];
int d=f2[m];
if(a-b>=nk&&c-d>=nk2)
{
return ;
}else
return ;
} int h[][],u[][],maxm,z[][];
int main()
{
// freopen("problem.in","r",stdin);
// freopen("problem.out","w",stdout);
scanf("%d%d",&t,&k); if(k==) k=,k2=,nk=,nk2=; //打表爆力分解质因数 分成 k,k2
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=;
else if(k==) k=,k2=,nk=,nk2=; for(int i=;i<=t;i++)
{
qu[i][]=read();
qu[i][]=read();
qu[i][]=min(qu[i][],qu[i][]);
if(qu[i][]<qu[i][]) qu[i][]=qu[i][];
if(qu[i][]>maxn) maxn=qu[i][];
if(qu[i][]>maxm) maxm=qu[i][];
}
//计算1到最大n 的每个数中有k 有多少个
for(int i=;i<=maxn;i++)
{
int j=,q=i;
while(q%k==) q/=k,j++;
g[i]=j;
}
//计算1到最大n 的每个数中有k2 有多少个
if(k2!=)
for(int i=;i<=maxn;i++)
{
int j=,q=i;
while(q%k2==) q/=k2,j++;
g2[i]=j;
}
memset(jy,0xfffffff,sizeof(jy));
//计算前缀 即 1到i 中有多少个k
for(int i=;i<=maxn;i++)
f[i]+=f[i-]+g[i];
//1到i 中有多少个k2
if(k2!=) for(int i=;i<=maxn;i++)
f2[i]+=f2[i-]+g2[i];
//计算z与u
for(int i=;i<=maxn;i++)
for(int j=;j<=i&&j<=maxm;j++)
z[i][j]=z[i][j-]+check(i,j),
u[i][j]=u[i-][min(i-,j)]+z[i][j]; for(int i=;i<=t;i++)
printf("%d\n",u[qu[i][]][qu[i][]]);
return ;
}