生成元(Digit Generator, ACMICPC Seoul 2005, UVa1583)

xiaoxiao2021-02-28  27

Written by Robert_Wang in Southwest University of Science And Technology.

如果x加上x的各个数字之和得到y,就说x是y的生成元。给出n(1≤n≤100000),求最小

生成元。无解输出0。例如,n=216,121,2005时的解分别为198,0,1979。

分析:对于给定的数n,需要从[1,n-1]去找他的最小元,所以在多次执行时会很耗时,如果我们事先做好[1,100000]

之后用的时候直接当一个函数查就行了。

#include<iostream> #include<algorithm> #define Max 100001 using namespace std; int ans[Max]; int main() { int i, j; int n, t; for (i = 1; i < Max; i++) { int x = i, y = i; while (x>0) { y += x % 10; x /= 10; }//I是y的元 if (!ans[y] || i < ans[y]) ans[y] = i;//如果y还没有最小生成元或者存在比其更小的生成元,就更新它 } cin >> t; while (t--) { cin >> n; cout << n << " 的最小生成元是:" << ans[n] << endl; } return 0; }
转载请注明原文地址: https://www.6miu.com/read-1450332.html

最新回复(0)