首页 > 代码库 > 51Nod 1016 水仙花数 V2(组合数学,枚举打表法)
51Nod 1016 水仙花数 V2(组合数学,枚举打表法)
1016 水仙花数 V2
基准时间限制：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个，所以，我们完全可以打表做题。那么剩下的问题就出现了，这些水仙花数是啥？
想知道这些数都是啥，可以选择两种手段，第一暴力解题，获得数据，但是我想这也忒复杂了，虽然是暴力解题，但是依然存在很多问题，就算你写出来代码，想获得所有的水仙花数依然需要很长很长时间等待哦，毕竟运算量惊人。
于是我只好选择第二种办法了，找度娘喽……
这是水仙花数……
1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 810 911 15312 37013 37114 40715 163416 820817 947418 5474819 9272720 9308421 54883422 174172523 421081824 980081725 992631526 2467805027 2467805128 8859347729 14651120830 47233597531 53449483632 91298515333 467930777434 3216404965035 3216404965136 4002839422537 4267829060338 4470863567939 4938855060640 8269391657841 9420459191442 2811644033596743 433828176939137044 433828176939137145 2189714258761207546 3564159420896413247 3587569906225003548 151784154330750503949 328958298444318703250 449812879116462486951 492927388592808882652 6310542598859969391653 12846864304373139125254 44917739914603869730755 2188769684112291628885856 2787969489305407447140557 2790786500997705256781458 2836128132131922946339859 3545259010403169193594360 17408800593806529302372261 18845148544789789603687562 23931366443004156935009363 155047533421450153908889464 155324216289377185066937865 370690799595547598864438066 370690799595547598864438167 442209511809589961945793868 12120499856361337240543806669 12127069600680131432843937670 12885179669648777784201278771 17465046449953137763163925472 17726545317179279236648976573 1460764061297198037261487308974 1900817413625427999501273474075 1900817413625427999501273474176 2386671643552397598039036929577 114503727576549102592429205034678 192789045714296069758063623663979 230909268261619030750969533891580 1733350999778224930872510396277281 18670996100153879010063413297699082 18670996100153879010063413297699183 112276328532937254159282290020459384 1263936951710379032894780720147839285 1267993778027227856630388559419692286 121916721962543412156973580360996601987 1281579207836605995509977054529612936788 11513221901876399256509559797397152240089 115132219018763992565095597973971522401
看着好爽啊，这么长……
接下来要考虑的问题就是比大小，这也好解决，位数不同的比位数，相同的再逐位比大小。大概就是这个样子吧。剩下的就没有什么难点了。
无耻的打表徒，来一发AC：
1 #include <stdio.h> 2 #include <string.h> 3 4 int compare(char *a, char *b, int len) 5 { 6 for (int i = 0; i < len; i++) 7 { 8 if (b[i] > a[i]) 9 {10 return 1;11 }12 else if (b[i] < a[i])13 {14 return 0;15 }16 }17 return 1;18 }19 20 int main(int argc, const char * argv[])21 {22 char NarNum[89][60] = {"0","1","2","3","4","5","6","7","8","9","153","370","371","407","1634","8208","9474","54748","92727","93084","548834","1741725","4210818","9800817","9926315","24678050","24678051","88593477","146511208","472335975","534494836","912985153","4679307774","32164049650","32164049651","40028394225","42678290603","44708635679","49388550606","82693916578","94204591914","28116440335967","4338281769391370","4338281769391371","21897142587612075","35641594208964132","35875699062250035","1517841543307505039","3289582984443187032","4498128791164624869","4929273885928088826","63105425988599693916","128468643043731391252","449177399146038697307","21887696841122916288858","27879694893054074471405","27907865009977052567814","28361281321319229463398","35452590104031691935943","174088005938065293023722","188451485447897896036875","239313664430041569350093","1550475334214501539088894","1553242162893771850669378","3706907995955475988644380","3706907995955475988644381","4422095118095899619457938","121204998563613372405438066","121270696006801314328439376","128851796696487777842012787","174650464499531377631639254","177265453171792792366489765","14607640612971980372614873089","19008174136254279995012734740","19008174136254279995012734741","23866716435523975980390369295","1145037275765491025924292050346","1927890457142960697580636236639","2309092682616190307509695338915","17333509997782249308725103962772","186709961001538790100634132976990","186709961001538790100634132976991","1122763285329372541592822900204593","12639369517103790328947807201478392","12679937780272278566303885594196922","1219167219625434121569735803609966019","12815792078366059955099770545296129367","115132219018763992565095597973971522400","115132219018763992565095597973971522401"};23 int NarNumLen;24 char num[60];25 scanf("%s", num);26 int NumLen = (int)strlen(num);27 for (int i = 0; i < 89; i++)28 {29 NarNumLen = (int)strlen(NarNum[i]);30 if ((NumLen == NarNumLen && compare(num, NarNum[i], NumLen)) || NumLen < NarNumLen)31 {32 printf("%s\n", NarNum[i]);33 return 0;34 }35 }36 37 puts("No Solution");38 return 0;39 }
51Nod 1016 水仙花数 V2(组合数学,枚举打表法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。