kurarrr's memooo

主に競プロ備忘録

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2

解法

a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い.
Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない.

定跡としてこの分布をとると,(つまり cnt[a] := aの現れる回数 とする)
全ての a<=b (a,bはcntのkey) についての全探索がO(K)となって間に合う.

ただし a==bのときは abがKの倍数になるならば cnt[a](cnt[a]-1) を足すことに注意(自分自身とは組にできないため)

コード