ZSTUoj 4433-Suffix Zeroes(暴力枚举)

这两天和队友聊了一下理工新生赛,提到我暴力枚举A掉的这题,干脆搞个题解了
时效性确实是 过了

题目:Suffix Zeroes

Description
这个游戏超休闲的~。现在你需要找一个自然数n,你找的自然数需要满足n!的末尾恰好有k个0(当然我们都是十进制下的数,n! = 123n)。比如: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算三个
  所以可以很直接地得到一个式子
这个除法是整数的 即int(ans/5)

  max等于10其实差不多了,我下面代码写得花里胡哨的max是一开始因为tle的改动,现在想想就10能改变什么
  再整理得
其实不太规范(因为除法结果不带小数)但是也近似了
  即有max越大,ans越接近4×k(用星号会用奇奇怪怪的问题所以不用了)
  等max=10的时候,5^max接近1e8,这个时候ans也不会比4×k大多少,所以可直接暴力枚举:

AC代码

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
#include<stdio.h>
#include<math.h>
int main() {
int T, b = 1, max, d = 1;
long k, k1 = 0, flag = 0, ans;
scanf("%d", &T);
while (T--) {
scanf("%ld", &k);
printf("Case %d: ", d++);
max = floor(log(k * 5) / log(5));
for (long i = k * 4; i <= k * 4 + 100; i++) {
for (int j = 1; j <= max; j++) {
b = b * 5;
k1 += (i / b);
}
b = 1;
if (k1 == k) {
printf("%ld\n", i);
flag = 1;
break;
}
k1 = 0;
}
if (flag == 0) printf("impossible\n");
flag = k1 = 0;
}
return 0;
}

  类似有一题,是在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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<iostream>
using namespace std;
int main() {
long n;
long long c, a = 1,ans=0;
while (~scanf("%ld", &n)) {
c = pow(n, 3);
for (int i = 1; i < 18; i++) {
a *= 9;
ans = ans + (c / a);
}
printf("%lld\n", ans);
a = 1;
ans = 0;
}
return 0;
}