NEFU118 n!后面有多少个0【算术基本定理】

题目链接：

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

题目大意：

问：计算N！末尾0的个数。(1 <= N <= 1000000000)。

思路：

N是100000000规模的数，直接计算结果，再统计0的个数显然不科学。将末尾0分解为2*5。

每一个0必然和一个因子5对应，但是一个数的因式分解中一个因子5不一定对应一个0。因为

还需要一个因子2，才能实现一一对应。

对于N!，在因式分解中，因子2的个数明显大于因子5的个数。所以如果存在一个因子5，那么

必然对应着N!末尾的一个0。这道题就变为了求N!中因子5的个数。由算术基本定理的性质(5)

可知：N!在素因子分解中素数p的幂为[N/p] + [N/p^2] + [N/p^3] + …，可以直接循环计算。

此时，5的幂就是N!中因子5的个数，也就是N!末尾0的个数。

附算术基本定理的定义和性质：

定理：

每个大于1的正整数N都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列。

正整数N的分解式 N = p1^α1 * p2^α2 * p3^α3 * … * pk^αk 称为N的标准分解式，其中

p1，p2，…，pk是素数，p1 < p2 < p3 < … < pk，且α1，α2，α3，…，αk是正整数。

性质：

(1)若N的标准素因子分解表达式为：N = p1^α1 * p2^α2 * p3^α3 * … * pk^αk，设d(N)

为N的挣银子个数， Φ(N)为N的所有因子之和，则有

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)设a = α1 * p2^α2 * … * pk^αk，b = p1^ β1 * p2^β2 * … * pk^βk，则有

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)如果a和b为实数，则

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

(4)如果a和b是正整数，则

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

(5)N!的素因子分解中的素数p的幂为

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

AC代码：

登录后复制

      
      

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