NEFU119 组合素数【算术基本定理】

题目链接：

​ ​http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=119​​

题目大意：

给你两个整数N和P，求出C(2*N，N)被素数p整数的次数。

思路：

由算术基本定理的性质(5)可得到N!被素数P整除的次数。

来看这道题，C(2*N，N) = (2*N)! / (N! * N!)。最终结果就是从(2*N)!能被素数P整除的

次数里边减去N!能被素数整除的次数*2。最终结果为：

[2*N/P] + [2*N/P^2] + … + [2*N/P^t] - 2*([N/P] + [N/P^2] + … + [N/P^t])。

其中次数t = logP(2*N)，即log10(2*N) / log10(P)。

AC代码：

登录后复制

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cstdio>
       
       

       
       #include<cstring>
       
       

       
       #include<cmath>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       int 
       
       T, 
       
       N, 
       
       P, 
       
       tag, 
       
       sum;
       
       
    
       
       cin 
       
       >> 
       
       T;
       
       
    
       
       while(
       
       T
       
       --)
       
       
    {
       
       

       
       
        
       
       cin 
       
       >> 
       
       N 
       
       >> 
       
       P;
       
       
        
       
       sum 
       
       = 
       
       0;
       
       
        
       
       double 
       
       s 
       
       = 
       
       0.0;
       
       
        
       
       s 
       
       = ( 
       
       log10(
       
       N
       
       *
       
       2.0)
       
       /
       
       log10(
       
       P
       
       *
       
       1.0) );
       
       
        
       
       tag 
       
       = 
       
       1;
       
       
        
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= (
       
       int)
       
       s; 
       
       ++
       
       i)
       
       
        {
       
       
            
       
       tag 
       
       *= 
       
       P;
       
       
            
       
       sum 
       
       += (
       
       int)(
       
       2
       
       *
       
       N
       
       /
       
       tag) 
       
       - 
       
       2
       
       *(
       
       int)(
       
       N
       
       /
       
       tag);
       
       
        }
       
       
        
       
       cout 
       
       << 
       
       sum 
       
       << 
       
       endl;
       
       
    }
       
       

       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.