微网站制作公司,微网站开发建设,娱乐公司网站建设价格,电子商务网站发展建设论文如果x加上x的各个数字之和得到y#xff0c;就说x是y的生成元。给出n#xff08;1≤n≤100000#xff09;#xff0c;求n的最小生成元。无解输出0。例如#xff0c;n216#xff0c;121#xff0c;2005时的解分别为198#xff0c;0#xff0c;1979。 【分析】 本题看起来…如果x加上x的各个数字之和得到y就说x是y的生成元。给出n1≤n≤100000求n的最小生成元。无解输出0。例如n2161212005时的解分别为19801979。 【分析】 本题看起来是个数学题实则不然。假设所求生成元为m。不难发现mn。换句话说只需枚举所有的mn看看有没有哪个数是n的生成元。 可惜这样做的效率并不高因为每次计算一个n的生成元都需要枚举n-1个数。 更快的方法是一次性枚举100000内的所有正整数x求出对应的yx是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;}
}
