C: ロト2 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder 問題概略 N個の整数A1~ANが与えられる。i<jとなるAi,Ajを選んだ時、２つの積がKの倍数となる組み合わせを求めよ 制約 1≦N≦200,000 1≦Ai≦109(1≦i≦N) 1≦K≦109 Ai, K はいずれも整数 解法 N^2では間に合わない。組み合わせ問題でよくあるまとめ上げを使う。 ２つの積がKの倍数になる -> Kの約数でないものは考えなくていいため、Aたちの中からKの約数だけを取り出し、それぞれ何個あるかを持っておく。 あと</jとなるai,ajを選んだ時、２つの積がkの倍数となる組み合わせを求めよ>…

C - すぬけそだて――ごはん―― 問題概略 A以上B以下の数から0個以上選ぶ時、それらが互いに素になる組み合わせはいくつか 制約 1≤A≤B≤10181≤A≤B≤1018 B−A≤35 解法 高々35個しかないので、偶数の中から0個か1つ選び、奇数の中から選ぶ数を全探索できる(18 * 2^1…