Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC096-D Five, Five Everywhere】5つ足して合成数とは

初見だと解けなかった問題

D - Five, Five Everywhere

問題

長さNの配列がある。要素はすべて異なる素数で、すべて55555以下である。この配列からどの5つを選んでも和が合成数となる。そのような配列を一つ見つけよ。Nは55以下。

方針

1つ見つけよ系は、何か特殊な法則を作って、それで一気にキメにかかるのが定石。

この場合、仮に5つ選んだものがすべて1(mod 5)だったら、和は5の倍数になるよねということに気づくことが必要。あとはエラトステネスで55555以下の素数を列挙して、5の倍数のものをピックするだけ。

実装

fn solve() {
    // dbg!(eratosthenes(99));
    input! {
        N:usize
    }
    let primes = eratosthenes(55555);
    let mut ans = vec![];
    for p in primes {
        if p%5==1 {
            ans.push(p.to_string());
            if ans.len() == N {
                break;
            }
        }
    }
    println!("{}",ans.connect(" "));
}

考察

これは直接的にはmodの問題ではないが、modの性質を活用した問題といえる。つまり、1 mod pのものをp個足したらpで割れるだろという性質。

他にも、modの性質を利用した問題は良く出る。

  • C - Remainder Minimization 2019: 掛け算に関する性質。i x j mod 2019 (L<=i,j<=R)の最小値を求めよ。これは、modの掛け算の周期性について知っていれば、iもjもたかだか2019個しか調べなくてよい
  • D - Candy Distribution: 差に関する性質。累積和がMの倍数 <=> 累積和を計算する時に使う値がmod Mの下で等しい