生成元
对于正整数N,N的数字总和定义为N本身及其数字的总和。当M 是N的数字总和,我们称N为M的生成元。 例如,245的数字总和为256(= 245 + 2 + 4 + 5)。因此,245是 256。 毫不奇怪,有些数字没有任何生成元,有些数字有多个生成元。例如,216的生成器是198和207。 您将编写一个程序来查找给定整数的最小生成元。 输入值 您的程序将从标准输入中读取。输入包含T个测试用例。测试次数 情况T在输入的第一行中给出。每个测试用例需要一行包含整数N的行, 1≤N≤100,000。 输出量 您的程序将写入标准输出。每个测试用例仅打印一行。该行是 每个测试用例包含一个N的生成元。如果N具有多个生成器,则打印最小的生成器。如果N 没有任何生成器,请打印“0”。
思路:
可以先用一个数组把1到100000之间的每个数是生成元的数保存在相应的位置,如数组第216个数保存198。如果没有生成元的数就用0保存。
代码:
#include <iostream>
#include <string>
#define max 100005
using namespace std;
int main() {
int an[max]={};
for(int i=;i<max;++i)
{
int x=i,y=i;
while(x>)
{
y+=x%;
x/=;
}
if(an[y]==||i<an[y]) an[y]=i;
}
int n;
cin>>n;
for(int i=;i<n;++i)
{
int m;
cin>>m;
cout<<an[m]<<endl;
}
return ;
}