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" });
}

---

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

---

なんだかのどが痛い。

---

今日のコミット。

• rust-sandbox 1 commit
  • twiq-light: Add test for tweet_length
• rust-atcoder 1 commit
  • agc018 a