51nod1016

1016 水仙花数 V2

1. 1 秒
2. 131,072 KB
3. 160 分
4. 6 级题

 

水仙花数是指一个 n 位数 ( n≥3 )，它的每个位上的数字的 n 次幂之和等于它本身。（例如：1^3 + 5^3 + 3^3 = 153，1634 = 1^4 + 6^4 + 3^4 + 4^4）。

给出一个整数M，求 >= M的最小的水仙花数。

收起

 

输入

一个整数M（10 <= M <= 10^60）

输出

输出>= M的最小的水仙花数，如果没有符合条件的水仙花数，则输出：No Solution

输入样例

300

输出样例

370

sol:好像标算是打表，感觉非常假，然后百度可知水仙花数一共只有89个，所以完全可行
贴上ak王xmy的打表代码以供参考

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M=1e9;

struct NUM{//压位高精

    int t;ll a[];

    friend NUM operator+(NUM x,NUM y){

        int i;

        for (i=;i<x.t || i<y.t || x.a[i];i++){

            if (i+>=x.t) x.a[i+]=;

            if (i<y.t) x.a[i]+=y.a[i];

            if (x.a[i]>=M) x.a[i+]++,x.a[i]-=M;

        }

        x.t=i;

        return x;

    }

    friend NUM operator*(NUM x,int y){

        int i;

        for (i=;i<x.t;i++) x.a[i]*=y;

        for (i=;i<x.t || x.a[i];i++){

            if (i+>=x.t) x.a[i+]=;

            x.a[i+]+=x.a[i]/M,x.a[i]%=M;

        }

        x.t=i;

        return x;

    }

}f[][],s;//f[i][j]=i^j

int n,a[],c[],d[],t1,t2,n1[],n2[];

void dfs(int x,int y,NUM s){

    t2=;

    memset(c,,sizeof(c));

    for (int i=;i<s.t;i++){

        int t=s.a[i];

        for (int j=;j<;j++) c[n2[t2++]=t%]++,t/=;

    }

    while (t2 && !n2[t2-]) t2--;

    if (t2>n) return;

    t1=;

    NUM tmp=s+f[x][n]*(n-y);//最大能得到的数

    for (int i=;i<tmp.t;i++){

        int t=tmp.a[i];

        for (int j=;j<;j++) n1[t1++]=t%,t/=;

    }

    while (t1 && !n1[t1-]) t1--;

    if (t1<n) return;

    if (x && t1==t2){

        memset(d,,sizeof(d));

        for (int i=n-;~i;i--)

            if (n1[i]!=n2[i]) break;

            else d[n1[i]]++;

        for (int i=x+;i<=;i++)

            if (a[i]<d[i]) return;

    }

    if (!x){

        for (int i=;i<=;i++)

            if (a[i]!=c[i]) return;

        for (int i=t2-;~i;i--) putchar(n2[i]|);

        puts("");

        return;

    }

    for (int i=;i<=n-y;i++){

        a[x]=i;

        dfs(x-,y+i,s);

        s=s+f[x][n];

    }

}

int main(){

    puts("");

    for (int i=;i<;i++){

        f[i][].t=f[i][].a[]=;

        for (int j=;j<;j++) f[i][j]=f[i][j-]*i;

    }

    for (int i=;i<=;i++) n=i,dfs(,,s);

}

make