51Nod-1016-水仙花数 V2

水仙花数是指一个 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

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

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

这是水仙花数……

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

看着好爽啊,这么长……

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

代码(C):

#include <stdio.h>
#include <string.h>

int compare(char *a, char *b, int len)
{
    for (int i = 0; i < len; i++)
    {
        if (b[i] > a[i])
        {
            return 1;
        }
        else if (b[i] < a[i])
        {
            return 0;
        }
    }
    return 1;
}

int main(int argc, const char * argv[])
{
    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"};
    int NarNumLen;
    char num[60];
    scanf("%s", num);
    int NumLen = (int)strlen(num);
    for (int i = 0; i < 89; i++)
    {
        NarNumLen = (int)strlen(NarNum[i]);
        if ((NumLen == NarNumLen && compare(num, NarNum[i], NumLen)) || NumLen < NarNumLen)
        {
            printf("%s\n", NarNum[i]);
            return 0;
        }
    }

    puts("No Solution");
    return 0;
}
全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务