Nefu119 combinatorial prime [basic theorem of arithmetic]

Topic link ：

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

The main idea of the topic ：

Here are two integers N and P, Find out C(2*N,N) Prime number p The number of integers .

Ideas ：

By the nature of the fundamental theorem of arithmetic (5) available N! Prime number P The number of divisions .

Look at this question ,C(2*N,N) = (2*N)! / (N! * N!). The end result is from (2*N)! Can be primed P Divisible

Subtract N! The number of times that can be divided by prime numbers *2. The final result is ：

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

The number of times t = logP(2*N), namely log10(2*N) / log10(P).

AC Code ：

Log in and copy

      
      

       
       #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.