C++生成元

生成元

对于正整数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]={0};
 for(int i=1;i<max;++i)
 {
     int x=i,y=i;
     while(x>0) 
     {
         y+=x%10;
         x/=10;
    }
     if(an[y]==0||i<an[y]) an[y]=i;
 }
 int n;
 cin>>n;
 for(int i=0;i<n;++i)
 {
     int m;
     cin>>m;
     cout<<an[m]<<endl;
 }
return 0;
}

原文链接: https://www.cnblogs.com/liushipeng648/p/12628604.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍