博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 12683 Odd and Even Zeroes(数学—找规律)
阅读量:5876 次
发布时间:2019-06-19

本文共 2800 字,大约阅读时间需要 9 分钟。

Time Limit: 1000 MS

In mathematics, the factorial of a positive integer number n is written as n! and is de ned as follows:
n! = 1 2 3 4 : : : (n  1) n =
∏n
i=1
i
The value of 0! is considered as 1. n! grows very rapidly with the increase of n. Some values of n!
are:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
10! = 3628800
14! = 87178291200
18! = 6402373705728000
22! = 1124000727777607680000
You can see that for some values of n, n! has odd number of trailing zeroes (eg 5!, 18!) and for some
values of n, n! has even number of trailing zeroes (eg 0!, 10!, 22!). Given the value of n, your job is to
nd how many of the values 0!; 1!; 2!; 3!; : : : ;(n  1)!; n! has even number of trailing zeroes.
Input
Input le contains at most 1000 lines of input. Each line contains an integer n (0 n 10
18
). Input
is terminated by a line containing a `-1'.
Output
For each line of input produce one line of output. This line contains an integer which denotes how
many of the numbers 0!; 1!; 2!; 3!; : : : ; n!, contains even number of trailing zeroes.
Sample Input
2
3
10
100
1000
2000
3000
10000
100000
200000
-1
Sample Output
3
4
6
61
525
1050
1551
5050
50250

100126

题意:给定一个数n。判定0! , 1! , 2!, ... , n!这(n+1)个阶乘有多少个末尾0的个数为偶数。 (0<=n<=10^18)

思路:i!末尾0个数取决于阶乘中5的个数。我们以5个数为一个总体。

1(5) 1(10) 1(15) 1(20) 2(25) 1(30) 1(35) 1(40) 1(45) 2(50) 1(55) 1(60) 1(65) 1(70) 2(75) 1(80) 1(85) 1(90) 1(95)  2(100) 1(105) 1(110)

1(115) 1(120) 3(125)  前一个数代表这个数中5的幂,后一个代表那个数。

我们将625曾经的数分组例如以下:

    1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3

    1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3

    1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3

    1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3

    1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 4

那么哪些段是满足末尾0的个数为偶数呢? 我们将第一行的段表示出来,(y)为是,(n)为否

    (y)1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 3

我们发现:

(1)已知直到出现第一个5的k次幂的大段,那么直到出现第一个5的(k+1)次幂的大段一定是5的k次幂的大段反复5段,且最后一段的最后

一个元素把k换成(k+1)即为直到出现第一个5的(k+1)次幂的大段。

(2)已知直到出现第一个5的k次幂的大段中每一个小段的y/n情况,那么能够推知第一个5的(k+1)次幂的大段的每一个小段的y/n情况。

     1.假设k是偶数。那么接下来的4个段与之前的段情况全然同样。

     2.假设k是奇数,那么接下来的4段中,第2和第4段与之前段的情况同样。

第1和第3段与之前段的情况正好相反。

设dp[ i ][ 0 ]表示分组后直到出现第一个5的i次幂时。之前满足末尾0的个数为偶数的段的个数。

   dp[ i ][ 1 ] 就是与上述情况相反的偶数的个数

那么

       dp[ i ][ 0 ]=5 *dp[ i-1 ][ 0 ]       i为奇数;

       dp[ i ][ 0 ]=3 *dp[ i ][ 0 ] + 2 *dp[ i ][ 1 ]     i为偶数;

      dp[ i ][ 1 ] = a [ i - 1 ] - dp[ i ][ 0 ];

预处理完dp数组之后,对于n,我们每次二分找不大于n的最大次幂区间, 最好还是设为k,x= n /  a[ k ],那么n -= a[ k ] * x; 同一时候依据k的奇

偶性,更新ans。同一时候我们设了一个变量now记录当前的状态.

#include 
#include
#include
#define LL long longusing namespace std;const int maxn=27;LL n,a[maxn],dp[maxn][2];void initial(){ LL t,sum=1; a[0]=1; for(int i=1;i
>n) { if(n==-1) break; solve(); } return 0;}

转载地址:http://cxzix.baihongyu.com/

你可能感兴趣的文章
PhalGo-Respones
查看>>
[MySQL 源码] MySQL drop table(压缩表)效率与流程分析
查看>>
activiti自定义流程之整合(六):获取我的申请任务
查看>>
高效Linux bash快捷键及alias总结
查看>>
css知识
查看>>
Struts 框架 之 Hello World
查看>>
【系统】如何控制cpu资源使用
查看>>
iOS8中的定位服务
查看>>
java String/StringBuilder 方法
查看>>
QTP学习笔记1
查看>>
【Linux网络编程】广播地址介绍
查看>>
iOS8新特性扩展(Extension)应用之二——分享插件
查看>>
数据迁移工具sqoop入门
查看>>
JDBC编程 之 增删改查
查看>>
《高效程序员的修炼》 读书笔记
查看>>
Android Animation动画详解(二): 组合动画特效
查看>>
《Netty权威指南》目录
查看>>
iGraph 2015双促复盘总结
查看>>
Android 开发第一弹:倒计时
查看>>
Linux Mac之间文件传输
查看>>