blog.bouzuya.net

2023-02-21 AGC018 の A を解いた

AGC018 : AtCoder Grand Contest 018 の A を解いた。

  • A - Getting Difference https://atcoder.jp/contests/agc018/tasks/agc018_a
    • 提出: https://atcoder.jp/contests/agc018/submissions/39092457
    • GCD(A) を考えたとき、当然 A_i は GCD(A) の倍数であり、操作によって A_i から任意の個数の GCD(A) を引いた値をつくれる、つまり一度 GCD(A) をつくってしまえば MAX(A) までの任意の GCD(A) の倍数を生成できる
    • 操作を繰り返すとユークリッドの互除法を実現できるので GCD(A) を得られる
    • K <= MAX(A) && K % GCD(A) == 0 ならつくれる対象の K になる
use proconio::input;

fn gcd(n: usize, m: usize) -> usize {
    if m == 0 {
        n
    } else {
        gcd(m, n % m)
    }
}

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
    };
    let max_a = a.iter().copied().max().unwrap();
    let mut g = a[0];
    for a_i in a.iter().copied().skip(1) {
        g = gcd(g, a_i);
    }
    let ans = k <= max_a && k % g == 0;
    println!("{}", if ans { "POSSIBLE" } else { "IMPOSSIBLE" });
}

子どもを眼科へ。ふたりを連れていくと疲れる。

なんだかのどが痛い。

今日のコミット。