結果
問題 | No.2074 Product is Square ? |
ユーザー |
|
提出日時 | 2023-07-30 02:27:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 794 ms / 2,000 ms |
コード長 | 2,524 bytes |
コンパイル時間 | 20,028 ms |
コンパイル使用メモリ | 378,200 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 15:22:23 |
合計ジャッジ時間 | 24,466 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
use std::io::{Write, BufWriter};// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr,) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);read_value!($next, [$t; len])}};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}fn gcd(mut x: i64, mut y: i64) -> i64 {while y != 0 {let r = x % y;x = y; y = r;}x.abs()}fn nth(a: i64, n: i64) -> i64 {let mut pass = 0;let mut fail = std::cmp::min(a, 1 << ((60 + n - 1) / n)) + 1;while fail - pass > 1 {let mid = (fail + pass) / 2;let mut tmp = 1i64;for _ in 0..n {tmp = tmp.saturating_mul(mid);}if tmp <= a {pass = mid;} else {fail = mid;}}pass}fn is_sq(a: i64) -> bool {let s = nth(a, 2);s * s == a}fn main() {let out = std::io::stdout();let mut out = BufWriter::new(out.lock());macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););}input! {n: usize,a: [[i64]; n],}for mut a in a {let n = a.len();loop {let mut changed = false;for i in 0..n {for j in 0..i {let g = gcd(a[i], a[j]);if g != 1 {a[i] /= g;a[j] /= g;changed = true;}}}if !changed {break;}}puts!("{}\n", if a.into_iter().all(is_sq) {"Yes"} else {"No"});}}