花朵数的简介和实现方法

一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。例如：当N=3时，153就满足条件，因为1^3+5^3+3^3=153，这样的数字也被称为水仙花数（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。当N=4时，1634满足条件，因为1^4+6^4+3^4+4^4=1634。当N=5时，92727满足条件。实际上，对N的每个取值，可能有多个数字满足条件。程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。#includeiostream#includestring.h#includemath.h#includetime.husingnamespacestd;voidmc(int*b,int*a);voidf(int*s,intn);voidg(int*f,int*a);intmain(){intk=0;intf1[10][21];memset(f1,0,sizeof(f1));intf2[10][21];memset(f2,0,sizeof(f2));inta[10],b[10];memset(a,0,sizeof(a));memset(b,0,sizeof(b));inth[21];memset(h,0,sizeof(h));inty[21]={-1};boolth=true;for(inti=0;i10;i++){f1[i][0]=i;f(f1[i],21);}clock_tbegin_time,end_time;begin_time=clock();for(a[0]=0;a[0]21;a[0]++)for(a[1]=0;a[1]21-a[0];a[1]++)for(a[2]=0;a[2]21-a[0]-a[1];a[2]++)for(a[3]=0;a[3]21-a[2]-a[0]-a[1];a[3]++)for(a[4]=0;a[4]21-a[3]-a[2]-a[1]-a[0];a[4]++)for(a[5]=0;a[5]21-a[4]-a[3]-a[2]-a[1]-a[0];a[5]++)for(a[6]=0;a[6]21-a[5]-a[4]-a[3]-a[2]-a[1]-a[0];a[6]++)for(a[7]=0;a[7]21-a[6]-a[5]-a[4]-a[3]-a[2]-a[1]-a[0];a[7]++)for(a[8]=0;a[8]21-a[7]-a[6]-a[5]-a[4]-a[3]-a[2]-a[1]-a[0];a[8]++){a[9]=21-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7]-a[8];if(a[9]=0||a[9]9)continue;intgh;for(inti=0;i10;i++){gh=0;for(intj=0;j21;j++){intt=f1[i][j]*a[i]+gh;f2[i][j]=t%10;gh=t/10;}}for(i=0;i10;i++){g(f2[i],h);}mc(b,h);for(i=0;i10;i++){if(b[i]!=a[i]){th=false;break;}}if(th==true){/*coutendl;for(i=0;i10;i++)couta[i];coutendl;for(i=0;i10;i++)coutb[i];coutendl;*/for(i=20;i=0;i--)couth[i];coutendl;}th=true;memset(b,0,sizeof(b));memset(h,0,sizeof(h));memset(f2,0,sizeof(f2));}end_time=clock();printf(\nTimeelapsed:%.3lf(ms)\n,(double)(end_time-begin_time));return0;}voidmc(int*b,int*a){for(inti=0;i21;i++){intn=a[i];switch(n){case0:b[0]++;break;case1:b[1]++;break;case2:b[2]++;break;case3:b[3]++;break;case4:b[4]++;break;case5:b[5]++;break;case6:b[6]++;break;case7:b[7]++;break;case8:b[8]++;break;case9:b[9]++;break;}}}voidf(int*s,intn){intc=fabs(s[0]),h=0;for(inti=0;i20;i++){h=0;for(intj=0;j21;j++){intt=fabs(s[j])*c+h;s[j]=t%10;h=t/10;}}}voidg(int*f,int*a){intc=0;for(inti=0;i21;i++){intt=f[i]+a[i]+c;a[i]=t%10;c=t/10;#includeiostream#includestring.h#includemath.h#includetime.husingnamespacestd;voidmc(int*b,int*a);voidf(int*s,intn);voidg(int*f,int*a);intmain(){intk=0;intf1[10][21];memset(f1,0,sizeof(f1));intf2[10][21];memset(f2,0,sizeof(f2));inta[10],b[10];memset(a,0,sizeof(a));memset(b,0,sizeof(b));inth[21];memset(h,0,sizeof(h));inty[21]={-1};boolth=true;for(inti=0;i10;i++){f1[i][0]=i;f(f1[i],21);}clock_tbegin_time,end_time;begin_time=clock();for(a[0]=0;a[0]21;a[0]++)for(a[1]=0;a[1]21-a[0];a[1]++)for(a[2]=0;a[2]21-a[0]-a[1];a[2]++)for(a[3]=0;a[3]21-a[2]-a[0]-a[1];a[3]++)for(a[4]=0;a[4]21-a[3]-a[2]-a[1]-a[0];a[4]++)for(a[5]=0;a[5]21-a[4]-a[3]-a[2]-a[1]-a[0];a[5]++)for(a[6]=0;a[6]21-a[5]-a[4]-a[3]-a[2]-a[1]-a[0];a[6]++)for(a[7]=0;a[7]21-a[6]-a[5]-a[4]-a[3]-a[2]-a[1]-a[0];a[7]++)for(a[8]=0;a[8]21-a[7]-a[6]-a[5]-a[4]-a[3]-a[2]-a[1]-a[0];a[8]++){a[9]=21-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7]-a[8];if(a[9]=0||a[9]9)continue;intgh;for(inti=0;i10;i++){gh=0;for(intj=0;j21;j++){intt=f1[i][j]*a[i]+gh;f2[i][j]=t%10;gh=t/10;}}for(i=0;i10;i++){g(f2[i],h);}mc(b,h);for(i=0;i10;i++){if(b[i]!=a[i]){th=false;break;}}if(th==true){/*coutendl;for(i=0;i10;i++)couta[i];coutendl;for(i=0;i10;i++)coutb[i];coutendl;*/for(i=20;i=0;i--)couth[i];coutendl;}th=true;memset(b,0,sizeof(b));memset(h,0,sizeof(h));memset(f2,0,sizeof(f2));}end_time=clock();printf(\nTimeelapsed:%.3lf(ms)\n,(double)(end_time-begin_time));return0;}voidmc(int*b,int*a){for(inti=0;i21;i++){intn=a[i];switch(n){case0:b[0]++;break;case1:b[1]++;break;case2:b[2]++;break;case3:b[3]++;break;case4:b[4]++;break;case5:b[5]++;break;case6:b[6]++;break;case7:b[7]++;break;case8:b[8]++;break;case9:b[9]++;break;}}}voidf(int*s,intn){intc=fabs(s[0]),h=0;for(inti=0;i20;i++){h=0;for(intj=0;j21;j++){intt=fabs(s[j])*c+h;s[j]=t%10;h=t/10;}}}voidg(int*f,int*a){intc=0;for(inti=0;i21;i++){intt=f[i]+a[i]+c;a[i]=t%10;c=t/10;}}#includesstream#includeiostream#includecstdlib#includectimeusingnamespacestd;templateclassTstringtostring(Ta){ostringstreamos;osa;returnos.str();}#defineN21typedefpairlonglong,longlongNUM;#defineMOD1000000000000000LL;NUMpow21[10][N+1];intsump[10][N+1];voidinit(){for(inti=0;i10;i++)for(intj=0;j=N;j++)sump[i][j]=i*j;for(inti=0;i10;i++){pow21[i][0].first=pow21[i][0].second=0;}pow21[0][1].first=pow21[0][1].second=0;for(inti=1;i10;i++){pow21[i][1].first=1;pow21[i][1].second=0;for(intj=0;jN;j++){pow21[i][1].first*=i;pow21[i][1].second*=i;pow21[i][1].second+=pow21[i][1].first/MOD;pow21[i][1].first%=MOD;}}for(intj=2;j=N;j++){for(inti=0;i10;i++){pow21[i][j].first=j*pow21[i][1].first;pow21[i][j].second=j*pow21[i][1].second;pow21[i][j].second+=pow21[i][j].first/MOD;pow21[i][j].first%=MOD;}}}intnumct[10],numct2[10];voidprint(NUMt){strings=t