组合素数
Problem:119
Time Limit:1000ms
Memory Limit:65536K
Description
小明的爸爸从外面旅游回来给她带来了一个礼物，小明高兴地跑回自己的房间，拆开一看是一个很大棋盘（非常大），小明有所失望。不过没过几天发现了大棋盘的好玩之处。从起点(0，0)走到终点(n,n)的非降路径数是C(2n,n)，现在小明随机取出1个素数p, 他想知道C(2n,n)恰好被p整除多少次？小明想了很长时间都没想出来，现在想请你帮助小明解决这个问题，对于你来说应该不难吧!
Input
有多组测试数据。
第一行是一个正整数T，表示测试数据的组数。接下来每组2个数分别是n和p的值，这里1<=n,p<=1000000000。
Output
对于每组测试数据，输出一行，给出C(2n,n)被素数p整除的次数，当整除不了的时候，次数为0。
Sample Input
2
2 2
2 3
Sample Output
1
1
这里的数据会很大，所以，不能直接计算，那么可以用公式
((2n/p)-2(n/p))+((2n/p^2)-2(n/p^2))+…+((2n/p^t)-2(n/p^t));
其中t=(log10(2*n)/log10(p));
#include <cstdio>
#include <cmath>
int main()
{int m;scanf("%d",&m);while(m --){int n,p;scanf("%d%d",&n,&p);double s= log10(2*n)/log10(p);int q;q=(int)s;int num=1;int sum=0;for(int a = 0;a < q ;a ++){num*=p;sum+=2*n/num-2*(n/num);}printf("%d\n",sum);}return 0;
}