結果
問題 |
No.1723 [Cherry 3rd Tune *] Dead on
|
ユーザー |
|
提出日時 | 2021-10-30 20:26:35 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 1,767 bytes |
コンパイル時間 | 12,691 ms |
コンパイル使用メモリ | 400,780 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-07 13:52:54 |
合計ジャッジ時間 | 14,663 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
use std::collections::HashMap; use std::io; fn main() { let v = input_nums(); let (x, a, y, b) = (v[0], v[1], v[2], v[3]); let xv = prime_factorization(x); let yv = prime_factorization(y); let x_hmp = get_pf_hashmap(&xv); let y_hmp = get_pf_hashmap(&yv); let mut result = true; for (k, v) in y_hmp { if k == 1 { result = true; break; } if !x_hmp.contains_key(&k) { result = false; break; } if x_hmp[&k] * a < v * b { result = false; break; } } println!("{}", if result { "Yes" } else { "No" }); } fn prime_factorization(mut num: u64) -> Vec<u64> { let mut v = Vec::new(); let mut div = 2; let max_div = if num >= 30 { (num as f64).sqrt() as u64 } else { num }; while div <= max_div { if num % div == 0 { v.push(div); num /= div; } else { div += 1; } } if v.len() == 0 { v.push(num); } v } fn get_pf_hashmap(pf_v: &Vec<u64>) -> HashMap<u64, u64> { let mut hm = HashMap::new(); let mut count = 0; let mut cor = 2; for i in 0..pf_v.len() { if cor == pf_v[i] { count += 1; } else { if count != 0 { hm.insert(cor, count); } cor = pf_v[i]; count = 1; } if i == pf_v.len() - 1 { hm.insert(cor, count); } } hm } fn input_nums() -> Vec<u64> { let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); let mut v = Vec::new(); for n in s.split_whitespace() { v.push(n.parse().unwrap()); } v }