nefu119组合素数

/* 题目描述：给出正整数n和素数p（1<n, p<1e9），问C(2*n , n)能整除p多少次 方法：C(2*n , n) = (2*n)!/(n! * n!)，因此答案就是2*n分解后p的指数减去2倍n分解后p的指数 根据定理，n！分解后p的指数为 k = [n / p] + [n / p^2] + [n / p^3] +... + 0 */ #pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cmath> #include<string> #include<sstream> #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-8; LL factor_times(LL n , LL p) { LL temp = p , sum = 0 ; while( n / temp >0){ sum += n / temp; temp *= p; } return sum; } int main() { int T; LL n,p; scanf("%d",&T); while(T--){ scanf("%lld %lld",&n , &p); LL ans1 = factor_times(2 * n , p); LL ans2 = factor_times(n , p); printf("%lld\n",ans1 - 2 * ans2); } return 0 ; }