ZSTUoj 4433-Suffix Zeroes（暴力枚举）

这两天和队友聊了一下理工新生赛，提到我暴力枚举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 算三个 　　所以可以很直接地得到一个式子

　　mx 等于 10 其实差不多了，我下面代码写得花里胡哨的 mx 是一开始因为 tle 的改动，现在想想就 10 能改变什么 　　再整理得

　　即有 mx 越大，ans 越接近 4×k（用星号会用奇奇怪怪的问题所以不用了） 　　等 mx=10 的时候，5^mx 接近 1e8，这个时候 ans 也不会比 4×k 大多少，所以可直接暴力枚举：

AC代码

#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代码

#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;
}