对于本题的因数m，只需要将其化为素因子的乘积形式，其中每一个素因子的个数为mi,之后只需要求得每一个素因子pi在组合数中的个数Ci，然后将取Ci/mi中的最小的那个，就是该因数在组合数中的个数。
代码如下：
/*
* fafu1079.c
*
* Created on: 2011-10-9
* Author: bjfuwangzhu
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define nmax 31625
int flag[nmax], prime[nmax], pfactor[nmax], cpfactor[nmax];
int plen, cplen;
//打素数表
void mkprime() {
int i, j;
memset(flag, -1, sizeof(flag));
for (i = 2, plen = 0; i < nmax; i++) {
if (flag[i]) {
prime[plen++] = i;
}
for (j = 0; (j < plen) && (i * prime[j] < nmax); j++) {
flag[i * prime[j]] = 0;
if (i % prime[j] == 0) {
break;
}
}
}
}
//将K化成素因子的乘积的形式
void findFactor(int k) {
int i, te, cnt;
te = (int) sqrt(k * 1.0);
for (i = 0, cplen = 0; (i < plen) && (prime[i] <= te); i++) {
if (k % prime[i] == 0) {
cnt = 0;
while (k % prime[i] == 0) {
cnt++;
k /= prime[i];
}
pfactor[cplen] = prime[i];
cpfactor[cplen++] = cnt;
}
}
if (k > 1) {
pfactor[cplen] = k;
cpfactor[cplen++] = 1;
}
}
//获得素因子p在1*2*··n中的个数
int getNum(int n, int m) {
int res;
res = 0;
while (n) {
res += n / m;
n /= m;
}
return res;
}
//获得素因子是在组合数中的个数，
//并凭借该素因子在因数k中的个数，得到该因数k在组合数中的个数
int cal(int i, int n, int m) {
int temp;
temp = getNum(n, pfactor[i]);
temp -= getNum(m, pfactor[i]);
temp -= getNum(n - m, pfactor[i]);
return temp / cpfactor[i];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int i, t, n, m, k, temp, res;
mkprime();
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &n, &m, &k);
findFactor(k);
for (i = 0, res = nmax; i < cplen; i++) {
temp = cal(i, n, m);
if (temp < res) {
res = temp;
}
}
printf("%d\n", res);
}
return 0;
}