本文共 1217 字，大约阅读时间需要 4 分钟。

突破口：一个很大的数，假设是20位，其每个数字的平方的和不超过2000，因此只要将2000以内的鸽子数找出来，打表就可以。

代码如下：

#include
   
    #include
    
     using namespace std;long long ge[150005];long long yes[2001]//yes记录2000以内的鸽子数bool search(int x,int y,int v)  //二分查找{    int m;    while(x
     
      v) y=m;        else x=m+1;    }    return false;}int p,q;int main(){    int Qn,i,j,cnt,k,sum;    ge[0]=0;    memset(yes,0,sizeof(yes));    memset(no,0,sizeof(no));    p=q=0;    for(i=1;i<=2000;i++)  //建表，找出2000内所有鸽子数    {        sum=cnt=0;  //sum表示各个数字平方之和，cnt辅助        j=i;        while(sum!=1)  //检查是否为鸽子数，是的话最终sum为1        {            sum=0;            while(j>0)            {                int t;                t=j%10; sum+=t*t; j/=10;            }            j=sum;            cnt++;            if(cnt>15) break;   //避免无限循坏，当计算超过15次（足够次数）就可以结束了。        }        if(sum==1) 			yes[p++]=i;    }    for(i=0;i
      
       0)        {            int t;            t=j%10;            sum+=t*t;            j/=10;        }        if(search(0,p,sum)) 			ge[k++]=i;	// printf("%d\n",i);    }	//printf("%d\n",k);    scanf("%d",&Q);    while(Q--)    {        scanf("%d",&k);        printf("%lld\n",ge[k-1]);    }    return 0;}
      
     
    
   

小结：数据一大，但也不是大到离谱，可以考虑打表。

转载地址：http://ofdci.baihongyu.com/