結果
問題 | No.2811 Calculation Within Sequence |
ユーザー |
|
提出日時 | 2024-07-19 21:27:21 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,308 bytes |
コンパイル時間 | 15,208 ms |
コンパイル使用メモリ | 378,192 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2024-07-19 21:27:55 |
合計ジャッジ時間 | 19,475 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 WA * 4 |
ソースコード
use anmitsu::number_theory::gcd;use proconio::{fastout, input};pub mod anmitsu {pub mod number_theory {/// Returns:/// gcd(a, b)////// Note:/// gcd(0, 0) = 0/// gcd(a, 0) = a/// gcd(a, b) >= 0/// gcd(a, a) == abs(a)/// gcd(a, b) == gcd(b, a)////// Complexity:/// O(log(min(abs(a), abs(b))))////// Exsamples:/// ```/// use anmitsu::math::number_theory::gcd;/// assert_eq!(gcd(0, 0), 0);/// assert_eq!(gcd(0, 1), 1);/// assert_eq!(gcd(4, 6), 2);/// assert_eq!(gcd(4, -6), 2);/// assert_eq!(gcd(-4, 6), 2);/// assert_eq!(gcd(-4, -6), 2);/// assert_eq!(gcd(2, 2), 2);/// assert_eq!(gcd(-2, -2), 2);/// ```pub fn gcd(mut a: i64, mut b: i64) -> u64 {while b != 0 {(a, b) = (b, a % b);}a.unsigned_abs()}/// Returns:/// (x, y): (i64, i64)/// s.t./// - gcd(a, b) = a * x + b * y/// - max(abs(x), abs(y)) <= max(abs(a), abs(b))////// Complexity:/// O(log(min(abs(a), abs(b))))////// References:/// - [超わかりやすい拡張ユークリッドの互除法 - 簡潔なQ](https://qnighy.hatenablog.com/entry/20091230/1262173513)////// Exsamples:/// ```/// use anmitsu::math::number_theory::extended_gcd;////// // gcd(10, 4) = 2 = 10 * 1 + 4 * (-2)/// assert_eq!(extended_gcd(10, 4), (1, -2));////// // gcd(0, 4) = 4 = 0 * 0 + 4 * 1/// assert_eq!(extended_gcd(0, 4), (0, 1));////// // gcd(0, 0) = 0 = 0 * 0 + 0 * 0/// assert_eq!(extended_gcd(0, 0), (0, 0));////// // gcd(-12, 7) = 1 = -12 * (-3) + 7 * (-5)/// assert_eq!(extended_gcd(-12, 7), (-3, -5));/// ```pub fn extended_gcd(a: i64, b: i64) -> (i64, i64) {if a == 0 && b == 0 {return (0, 0);} else if a == 0 {return (0, if b >= 0 { 1 } else { -1 });} else if b == 0 {return (if a >= 0 { 1 } else { -1 }, 0);}let (mut xs, mut ys, mut s) = (1, 0, a);let (mut xt, mut yt, mut t) = (0, 1, b);while s % t != 0 {let q = s / t;let (u, xu, yu) = (s - q * t, xs - q * xt, ys - q * yt);(xs, ys, xt, yt) = (xt, yt, xu, yu);(s, t) = (t, u);}if t < 0 {(-xt, -yt)} else {(xt, yt)}}}}#[fastout]fn main() {input! {a: usize, b: usize,t: [usize; a],s: [usize; b],}if a < b && (a..b).any(|i| s[i] != 0) {println!("No");return;}let mut g = t[0];for i in 1..a {g = gcd(g as i64, t[i] as i64) as usize;}if (0..a).any(|i| t[i].abs_diff(*s.get(i).unwrap_or(&0)) % g != 0) {println!("No");} else {println!("Yes");}}