NEFU118 n! How many zeros are there after [basic theorem of arithmetic]

Topic link ：

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

The main idea of the topic ：

ask ： Calculation N！ At the end of 0 The number of .(1 <= N <= 1000000000).

Ideas ：

N yes 100000000 Number of scales , Direct calculation result , Re statistics 0 The number of is obviously unscientific . At the end 0 Decompose into 2*5.

every last 0 There must be a factor 5 Corresponding , But a factor in the factorization of a number 5 It doesn't necessarily correspond to one 0. because

Another factor is needed 2, To achieve one-to-one correspondence .

about N!, In factorization , factor 2 The number of is significantly larger than the factor 5 The number of . So if there is a factor 5, that

It must correspond to N! Last one 0. This problem becomes to find N! Medium factor 5 The number of . By the nature of the fundamental theorem of arithmetic (5)

You know ：N! In prime factorization, prime numbers p The power of is [N/p] + [N/p^2] + [N/p^3] + …, You can directly cycle .

here ,5 It's a power of N! Medium factor 5 The number of , That is to say N! At the end of 0 The number of .

The definition and properties of the basic theorem of arithmetic are attached ：

Theorem ：

Each is greater than 1 The positive integer N Can be uniquely written as the product of primes , The prime factors in the product are arranged in non descending order .

Positive integer N Decomposition of N = p1^α1 * p2^α2 * p3^α3 * … * pk^αk be called N The standard decomposition of , among

p1,p2,…,pk Prime number ,p1 < p2 < p3 < … < pk, And α1,α2,α3,…,αk It's a positive integer. .

nature ：

(1) if N The standard prime factorization expression of is ：N = p1^α1 * p2^α2 * p3^α3 * … * pk^αk, set up d(N)

by N Number of silver earned , Φ(N) by N The sum of all the factors of , Then there are

d(N) = (α1 + 1) * (α2 + 1) * (α3 + 1) * … * (αk + 1)

Φ(N) = ( p1^(α1 + 1) )/(p1 - 1) * ( p2^(α2 + 1) )/(p2 - 1) * … * ( pk^(αk + 1) )/(pk - 1)

(2) set up a = α1 * p2^α2 * … * pk^αk,b = p1^ β1 * p2^β2 * … * pk^βk, Then there are

gcd(a,b) = p1^min(α1,β1) * p2^min(α2,β2) * … * pk^min(αk,βk)

lcm(a,b) = p1^max(α1,β1) * p2^max(α2,β2) * … * pk^max(αk,βk)

(3) If a and b It's a real number , be

max( gcd(a,b) ) + min( gcd(a,b) ) = a + b

(4) If a and b It's a positive integer. , be

lcm(a,b) = a*b/gcd(a,b)

(5)N! Prime numbers in the prime factorization of p The power of is

[N/p] + [N/p^2] + [N/p^3] + …

AC Code ：

Log in and copy

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cstdio>
       
       

       
       #include<cstring>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       int 
       
       T,
       
       N;
       
       
    
       
       cin 
       
       >> 
       
       T;
       
       
    
       
       while(
       
       T
       
       --)
       
       
    {
       
       
        
       
       cin 
       
       >> 
       
       N;
       
       
        
       
       int 
       
       t,
       
       five,
       
       sum;
       
       
        
       
       t 
       
       = 
       
       N;
       
       
        
       
       five 
       
       = 
       
       5;
       
       
        
       
       sum 
       
       = 
       
       0;
       
       
        
       
       while(
       
       five 
       
       <= 
       
       t)
       
       
        {
       
       
            
       
       sum 
       
       = 
       
       sum 
       
       + 
       
       t
       
       /
       
       five;
       
       
            
       
       five 
       
       *= 
       
       5;
       
       
        }
       
       
        
       
       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.