title: ZSTUoj 4433-Suffix Zeroes（暴力枚舉）
date: 2019-03-16 21:01:55
tags:
- acm
- 浙理2018新生賽
category: w
這兩天和隊(duì)友聊了一下理工新生賽，提到我暴力枚舉我A掉的這題，干脆搞個(gè)題解了
時(shí)效性確實(shí)是 過了
題目：Suffix Zeroes
Description
這個(gè)游戲超休閑的~?，F(xiàn)在你需要找一個(gè)自然數(shù)n，你找的自然數(shù)需要滿足n!的末尾恰好有k個(gè)0（當(dāng)然我們都是十進(jìn)制下的數(shù)，n! = 123…n）。比如：5！= 120，尾部恰好有一個(gè)0。
Input
先輸入T，代表有T組數(shù)據(jù)（T ≤10000）
接下來(lái)的T行每一行都包括一個(gè)數(shù)字k（1≤k≤108）。具體含義請(qǐng)見題意。
Output
如果能找到這樣的數(shù)，請(qǐng)輸出滿足條件的最小的自然數(shù)n，如果不存在這樣的自然數(shù)，請(qǐng)輸出impossible。
Sample Input
2
1
5
Sample Output
Case 1: 5
Case 2: impossible
首先，題目意思就是找5（2比5多很多所以不必考慮2），有幾個(gè)0就是有幾個(gè)5
25算兩個(gè)5,50算兩個(gè)，125算三個(gè)
所以可以很直接地得到一個(gè)式子
max等于10其實(shí)差不多了，我下面代碼寫得花里胡哨的max是一開始因?yàn)閠le的改動(dòng)，現(xiàn)在想想就10能改變什么
再整理得
即有max越大，ans越接近4×k（用星號(hào)會(huì)用奇奇怪怪的問題所以不用了）
等max=10的時(shí)候，5^max接近1e8，這個(gè)時(shí)候ans也不會(huì)比4×k大多少，所以可直接暴力枚舉：
AC代碼
{% codeblock lang:cpp %}
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;
}
{% endcodeblock %}
類似有一題，是在HDU的HelloWorld社團(tuán)的比賽上（但是這題賊簡(jiǎn)單）：
題目2：這是一道簡(jiǎn)單的數(shù)學(xué)題
Problem Description
“今晚你會(huì)成為我的人！”
電視里傳出這樣的聲音，小明和小紅執(zhí)手相看，含情脈脈，四目相對(duì)。
小紅紅著臉：“你愛我嗎？”
小明：“當(dāng)然！”
小紅：“那你能告訴我你有多少個(gè)前女友嗎？”
小明：“別問，問就爆炸?！?br> 小紅：“老娘給你臉了，說(shuō)！??！”
小明腦補(bǔ)著該說(shuō)有幾個(gè)比較合適，他知道小紅有個(gè)習(xí)慣，就是特別喜歡不斷重復(fù)計(jì)算n?n?n里有多少個(gè)9，于是，他開始不斷枚舉n，以便讓小紅沉迷于計(jì)算，而不追究。
小紅對(duì)于n里有多少個(gè)9的定義：從1到n的每一個(gè)數(shù)能整除9的次數(shù)相加，如：9里有一個(gè)9（9/9），18里有兩個(gè)9（9/9，18/9），81里有10個(gè)9（9/9，18/9，27/9，36/9，45/9，54/9，63/9，72/9，81/9/9）
Input
多組測(cè)試數(shù)據(jù)，每組占一行。
每行一個(gè)n（1<=n<=100000）
Output
每行輸出一個(gè)整數(shù)，表示n?n?n中有多少個(gè)9
Sample Input
1
3
4
Sample Output
0
3
7
AC代碼
{% codeblock lang:cpp %}
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;
}
{% endcodeblock %}
