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 8
10 9
11 153
12 370
13 371
14 407
15 1634
16 8208
17 9474
18 54748
19 92727
20 93084
21 548834
22 1741725
23 4210818
24 9800817
25 9926315
26 24678050
27 24678051
28 88593477
29 146511208
30 472335975
31 534494836
32 912985153
33 4679307774
34 32164049650
35 32164049651
36 40028394225
37 42678290603
38 44708635679
39 49388550606
40 82693916578
41 94204591914
42 28116440335967
43 4338281769391370
44 4338281769391371
45 21897142587612075
46 35641594208964132
47 35875699062250035
48 1517841543307505039
49 3289582984443187032
50 4498128791164624869
51 4929273885928088826
52 63105425988599693916
53 128468643043731391252
54 449177399146038697307
55 21887696841122916288858
56 27879694893054074471405
57 27907865009977052567814
58 28361281321319229463398
59 35452590104031691935943
60 174088005938065293023722
61 188451485447897896036875
62 239313664430041569350093
63 1550475334214501539088894
64 1553242162893771850669378
65 3706907995955475988644380
66 3706907995955475988644381
67 4422095118095899619457938
68 121204998563613372405438066
69 121270696006801314328439376
70 128851796696487777842012787
71 174650464499531377631639254
72 177265453171792792366489765
73 14607640612971980372614873089
74 19008174136254279995012734740
75 19008174136254279995012734741
76 23866716435523975980390369295
77 1145037275765491025924292050346
78 1927890457142960697580636236639
79 2309092682616190307509695338915
80 17333509997782249308725103962772
81 186709961001538790100634132976990
82 186709961001538790100634132976991
83 1122763285329372541592822900204593
84 12639369517103790328947807201478392
85 12679937780272278566303885594196922
86 1219167219625434121569735803609966019
87 12815792078366059955099770545296129367
88 115132219018763992565095597973971522400
89 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1823 音乐会的等待

题目描述 N个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。队列中任意两个人A和B,如果他们是相邻或他们之间没有人比...

39513
来自专栏海天一树

2015年第二十一届全国青少年信息学奥林匹克联赛初赛普及组C++详细答案

https://wenku.baidu.com/view/76e5f672284ac850ad0242f3.html?from=search

1792
来自专栏Petrichor的专栏

numpy库 简介

  NumPy 是一个 Python 包。 它代表 “Numeric Python”。 它是一个由多维数组对象和用于处理数组的例程集合组成的库。

2212
来自专栏AILearning

Apache Spark 2.2.0 中文文档 - GraphX Programming Guide | ApacheCN

GraphX Programming Guide 概述 入门 属性 Graph 示例属性 Graph Graph 运算符 运算符的汇总表 P...

6058
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K5
来自专栏java系列博客

UML类图

3063
来自专栏racaljk

Leetcode 70. Climbing Stairs 爬楼梯 (递归,记忆化,动态规划)

在第0阶,可以选择走到第1阶或者第2阶,第1阶可以走第2阶或者第3阶,第二阶可以走第3阶或者第4阶...。如此继续就生成了上图递归解答树。注意如果直接递归会超时...

3503
来自专栏从零开始学自动化测试

python笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

3419
来自专栏androidBlog

快速排序的相关算法题(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

2391
来自专栏牛客网

头条实习面经

【每日一语】真实人生中,我们往往在大势底定无可更改时才迟迟进场,却又在胜败未分的浑沌中提早离席。——翁贝托·埃科《开头与结尾》

1352

扫码关注云+社区

领取腾讯云代金券