欢迎访问https://blog.csdn.net/lxt_Lucia～～
宇宙第一小仙女\(^o^)/～～萌量爆表求带飞=≡Σ((( つ^o^)つ~ dalao们点个关注呗～～
----------------------------------------我只是一条可爱哒分界线-------------------------------------------
一、问题：
Description
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
鸽子数字由以下过程定义：从任何正整数开始，将数字替换为其各个数位的平方和，并重复该过程，直到该数字等于1。如果不能，则这个数字不是鸽子数。
例如7是鸽子数，因为7->49->97->130->10->1。（7*7=49,4*4+9*9=97,9*9+7*7=130....如此类推）
显然1是第一个鸽子数。
有Q个询问，每个询问给出一个数k，你需要输出第k个鸽子数。
Input
第一行一个Q，代表询问的个数（Q<=100000）
接下来Q行，每行一个数字k（k<150000）
Output
每行输出一个数，代表第k个鸽子数。
Sample Input
2
1
2
Sample Output
1
7
二、题意：
将某数的各个数位的平方和相加，不断重复该过程，如果能使得某个和1，则为鸽子数。
定义1是第一个鸽子数，问第k个鸽子数是多少。
三、思路：
这个题很容易T，两个思路：
1）暴力。将前150000个鸽子树打出来，求第 n 个直接输出a [ n ] 。可以过，但是如果全打出来初始化数组里代码长度会超。
2）先判前810个再操作。假设一个数是最大的十位数，即9999999999，它的平方和是810，可以先判 1 - 810 中有哪些数字为鸽子数（害怕.jpg就判1000个也行）。接下来对每个数进行第一次操作，结果也一定在810以内，直接判断是否为鸽子数即可，若第一次操作后为鸽子数，则该数操作下去一定也是鸽子数。
注意：有个小技巧，若出现{ 4，16，20，37，32，58，89，145}这几个数，一定不是鸽子数。可以直接判断是否有4出现，有4出现一定不为鸽子数。
四、代码：
思路一：暴力
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define read(x) scanf("%d", &x)
#define fori(a,b) for(int i=a; i<=b; i++)
using namespace std;
typedef long long LL;
int main()
{
int a[150010],T,n,sum,cnt=0;
a[++cnt] = 1;
fori(2, 1050000)
{
n=i;
while(n!=1 && n!=4)
{
sum=0;
while(n)
{
sum += (n%10)*(n%10);
n /= 10;
}
n = sum;
}
if(n == 1)
a[++cnt] = i;
if(cnt == 150000)
break;
}
read(T);
while(T--)
{
read(n);
printf("%d\n",a[n]);
}
return 0;
}
思路二：先判再操作：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define read(x) scanf("%d", &x)
#define fori(a,b) for(int i=a; i<=b; i++)
using namespace std;
typedef long long LL;
int mark[1005];
int test(int k)
{
int cnt = 0;
while (k != 1 && cnt < 1000)
{
int tmp = 0;
while (k != 0)
{
tmp += (k % 10) * (k % 10);
k /= 10;
}
k = tmp;
cnt++;
}
return k==1;
}
int a[150005];
int main()
{
int T, n, k, j=0;
fori(0, 999)
if(test(i))
mark[i] = 1;
fori(1, 149999)
{
k = j;
int tmp = 0;
while(k != 0)
{
tmp += (k % 10) * (k % 10);
k /= 10;
}
if(mark[tmp]==1)
{
a[i] = j;
i++;
}
j++;
}
read(T);
while(T--)
{
read(n);
printf("%d\n",a[n]);
}
return 0;
}
------------------------------------------我也是有底线的----------------------------------------------------
欢迎访问https://blog.csdn.net/lxt_Lucia～～
宇宙第一小仙女\(^o^)/～～萌量爆表求带飞=≡Σ((( つ^o^)つ~ dalao们点个关注呗～～
