小皮搭建本地网站,wordpress网站图片,设计站,北京网络技术有限公司题目 如果x加上x的各个数字之和得到y#xff0c;也就是说x是y的生成元。给出n(1n100000)#xff0c;求最小生成元。无解则输出0。
输入输出样例
输入
3
216
121
2005输出
198
0
1979思路 要想解决这个题目#xff0c;只需要对每一个输入的值从1开始遍历找到小于…题目 如果x加上x的各个数字之和得到y也就是说x是y的生成元。给出n(1n100000)求最小生成元。无解则输出0。
输入输出样例
输入
3
216
121
2005输出
198
0
1979思路 要想解决这个题目只需要对每一个输入的值从1开始遍历找到小于它自身的生成元取最小的即可但是这样的话每一个输入都需要枚举一次效率太低。更好的方法是我们一次性把1到100000内的所有正整数的最小生成元都求出来然后对于每一个输入直接查表即可。
代码
#includestdio.h
#includestring.h
#define maxn 100005//大小比较大的数组定义在主函数外面防止出现异常
int ans[maxn];
int main(){int T,n;memset(ans,0,sizeof(ans));//将数组每一个的值初始化为0 int m1;for(m1;mmaxn;m){//计算1到100000内的所有整数的最小生成元 int xm,ym;while(x0){yx%10;x/10;}if(ans[y]0||mans[y]){//如果当前数的生成元还没有计算或者后面计算出来的生成元比目前的生成元小那么改为当前值 ans[y]m;}}//接下来对于各种输入直接查表即可 scanf(%d,T);while(T--){scanf(%d,n);printf(%d\n,ans[n]);}return 0;
} 这个题目的重点就是打表法的使用。
