组合素数
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
从(0,0)出发到(n,n) 一共要向下移动n步 向右移动n步 一共移动2n步 2n步中选择n步向下走 其余n步向右走 所以一共有C(2n,n)种情况
不难发现C(2n,n)里 2n!能约去2个n!的因子 所以求出2n!包含的p的因子数 - 2*(n!包含的p的因子数)就是答案
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<math.h>
#include<list>
#include<cstring>
#include<fstream>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define INF 1000000007
#define pll pair<ll,ll>
#define pid pair<int,double>
ll slove(ll n,ll p){
ll ans=
0,divi=p;
while(divi<=n){
ans+=n/divi;
divi*=p;
}
return ans;
}
int main()
{
int T;
ll n,p;
scanf(
"%d",&T);
while(T--){
scanf(
"%lld%lld",&n,&p);
printf(
"%lld\n",slove(
2*n,p)-
2*slove(n,p));
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1000138.html