51Nod 1016 水仙花数 V2(组合数学,枚举打表法)

时间:2022-07-20 04:49:25
基准时间限制:1 秒 空间限制:131072 KB 分值: 160        
难度:6级算法题
               
水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身。(例如:1^3 + 5^3 + 3^3 = 153,1634 = 1^4 + 6^4 + 3^4 + 4^4)。
给出一个整数M,求 >= M的最小的水仙花数。
 
Input
一个整数M(10 <= M <= 10^60)
Output
输出>= M的最小的水仙花数,如果没有符合条件的水仙花数,则输出:No Solution
Input示例
300
Output示例
370
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1016
分析:

一道賊变态的题,如果按常规出牌,绝对做不出来,必然会超时,或者说,我肯定是做不成的。
但是如果投机取巧,那么这就是一道很简单的题,虽然它数据范围高达60位,但是水仙花数却是有限的,只有89个,所以,我们完全可以打表做题。那么剩下的问题就出现了,这些水仙花数是啥?

想知道这些数都是啥,可以选择两种手段,第一暴力解题,获得数据,但是我想这也忒复杂了,虽然是暴力解题,但是依然存在很多问题,就算你写出来代码,想获得所有的水仙花数依然需要很长很长时间等待哦,毕竟运算量惊人。
于是我只好选择第二种办法了,找度娘喽……

这是水仙花数……


看着好爽啊,这么长……

接下来要考虑的问题就是比大小,这也好解决,位数不同的比位数,相同的再逐位比大小。大概就是这个样子吧。剩下的就没有什么难点了。

无耻的打表徒,来一发AC:

 #include <stdio.h>
#include <string.h> int compare(char *a, char *b, int len)
{
for (int i = ; i < len; i++)
{
if (b[i] > a[i])
{
return ;
}
else if (b[i] < a[i])
{
return ;
}
}
return ;
} int main(int argc, const char * argv[])
{
char NarNum[][] = {"","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""};
int NarNumLen;
char num[];
scanf("%s", num);
int NumLen = (int)strlen(num);
for (int i = ; i < ; i++)
{
NarNumLen = (int)strlen(NarNum[i]);
if ((NumLen == NarNumLen && compare(num, NarNum[i], NumLen)) || NumLen < NarNumLen)
{
printf("%s\n", NarNum[i]);
return ;
}
} puts("No Solution");
return ;
}