「みんなのプロコン 2018」決勝 A - Uncommon
問題概要
個の異なる整数
と整数
が与えられる。
以上
以下のそれぞれの整数
について、
のうち
と互いに素であるものの個数を求めよ。
制約
解法
ある数 について、
のうち
と互いに素であるものの個数を求めるとき、愚直に1つずつ試して
でやると全体で
となりTLEする。
よって、互いに素であるものをまとめて計算することを考える。
6と互いに素なものは2の倍数でも3の倍数でもないものであるということを考えると、 と互いに素であるものは、
の約数の倍数を全体から引いたものであると考えられる。
前計算として、
f[ ] :=
のうち
の倍数であるものの個数
を求めてあげることで、包除原理を使って と互いに素であるものの個数は高速に求めることができる。
