这两天和队友聊了一下理工新生赛,提到我暴力枚举A掉的这题,干脆搞个题解了
时效性确实是 过了
题目:Suffix Zeroes
Description
这个游戏超休闲的~。现在你需要找一个自然数n,你找的自然数需要满足n!的末尾恰好有k个0(当然我们都是十进制下的数,n! = 123…n)。比如:5!= 120,尾部恰好有一个0。
Input
先输入T,代表有T组数据(T ≤10000)
接下来的T行每一行都包括一个数字k(1≤k≤108)。具体含义请见题意。
Output
如果能找到这样的数,请输出满足条件的最小的自然数n,如果不存在这样的自然数,请输出impossible。
Sample Input
2
1
5
Sample Output
Case 1: 5
Case 2: impossible
首先,题目意思就是找5(2比5多很多所以不必考虑2),有几个0就是有几个5
25算两个5,50算两个,125算三个
所以可以很直接地得到一个式子
max等于10其实差不多了,我下面代码写得花里胡哨的max是一开始因为tle的改动,现在想想就10能改变什么
再整理得
即有max越大,ans越接近4×k(用星号会用奇奇怪怪的问题所以不用了)
等max=10的时候,5^max接近1e8,这个时候ans也不会比4×k大多少,所以可直接暴力枚举:
AC代码
1 |
|
类似有一题,是在HDU的HelloWorld社团的比赛上(但是这题贼简单):
题目2:这是一道简单的数学题
Problem Description
“今晚你会成为我的人!”
电视里传出这样的声音,小明和小红执手相看,含情脉脉,四目相对。
小红红着脸:“你爱我吗?”
小明:“当然!”
小红:“那你能告诉我你有多少个前女友吗?”
小明:“别问,问就爆炸。”
小红:“老娘给你脸了,说!!!”
小明脑补着该说有几个比较合适,他知道小红有个习惯,就是特别喜欢不断重复计算n∗n∗n里有多少个9,于是,他开始不断枚举n,以便让小红沉迷于计算,而不追究。
小红对于n里有多少个9的定义:从1到n的每一个数能整除9的次数相加,如:9里有一个9(9/9),18里有两个9(9/9,18/9),81里有10个9(9/9,18/9,27/9,36/9,45/9,54/9,63/9,72/9,81/9/9)
Input
多组测试数据,每组占一行。
每行一个n(1<=n<=100000)
Output
每行输出一个整数,表示n∗n∗n中有多少个9
Sample Input
1
3
4
Sample Output
0
3
7
AC代码
1 |
|
近期评论