南浔区建设局 网站互联网推广运营

如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求n的最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198，0，1979。
【分析】
本题看起来是个数学题，实则不然。假设所求生成元为m。不难发现m<n。换句话说，只需枚举所有的m<n，看看有没有哪个数是n的生成元。
可惜这样做的效率并不高，因为每次计算一个n的生成元都需要枚举n-1个数。
更快的方法是一次性枚举100000内的所有正整数x，求出对应的y，x是y的最小生成元，最后查表即可。

解法：

use std::io;
fn main() {let mut ans = vec![0; 100000 + 50];for i in 1..=100000 {let mut x = i;let mut y = i;while x > 0 {y += x % 10;x /= 10;}if ans[y] == 0 || i < ans[y] {ans[y] = i;}}let mut buf = String::new();io::stdin().read_line(&mut buf).unwrap();let mut cnt: usize = buf.trim().parse().unwrap();while cnt > 0 {let mut buf = String::new();io::stdin().read_line(&mut buf).unwrap();let y: usize = buf.trim().parse().unwrap();println!("{}", ans[y]);cnt -= 1;}
}