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)
  mx 等于 10 其实差不多了,我下面代码写得花里胡哨的 mx 是一开始因为 tle 的改动,现在想想就 10 能改变什么
  再整理得
其实不太规范(因为除法结果不带小数)但是也近似了
  即有 mx 越大,ans 越接近 4×k(用星号会用奇奇怪怪的问题所以不用了)
  等 mx=10 的时候,5^mx 接近 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, mx, d = 1;
int k, k1 = 0, flag = 0, ans;
scanf("%d", &T);
while (T--) {
scanf("%d", &k);
printf("Case %d: ", d++);
mx = floor(log(k * 5) / log(5));
for (int i = k * 4; i <= k * 4 + 100; i++) {
for (int j = 1; j <= mx; j++) {
b = b * 5;
k1 += (i / b);
}
b = 1;
if (k1 == k) {
printf("%d\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
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<iostream>
using namespace std;
int main() {
long long n, c, a = 1,ans=0;
while (~scanf("%lld", &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;
}