DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2
思考過程
与えられた整数のそれぞれについて，他の整数
のそれぞれと積を取り，
の倍数であるか確認する解法がまず思いつきます．
が，計算量がO(
)になり，今回の入力サイズは
となるのでTLEしてしまいます．
ここでサンプル1を見てみましょう．
4 6 1 3 2 6
積を考えたいので，それぞれの要素に何をかければの倍数になるか考えます．
すると，
には
をかければいいことに気づきます．
は，
の約数です．必要そうなので，ここら辺で
の約数をとりあえず列挙しておきます．
では前処理として，約数ごとに
番目以降のその約数の個数を計算して，配列に保存しておけばいいのではないでしょうか．
これができたら，
を順にみていって，かけたらいい
の個数が
で求まり，答えがわかります．
前処理をした配列を値とし，対応する約数をキーとした辞書を持っておけば実装できそうです！
しかし残念ながらこれも前処理に
かかり，今回の入力だとTLEしてしまいます…．
解法
の約数について考えるのはいいことでした．さらに
の約数なら高々1500個くらいで抑えられるので1，
ならしていいです．ここで，
はi番目の
の約数とします．そして，
を
との最大公約数として持つAの要素の個数を，
ごとに数えておきます2．
以降，を
との最大公約数として持つAの要素の個数の
の個数と単に言います．
と
の個数の積を取ると，
と
の積を因数に持つペアの個数だということを発想します．ここは例を考えるとわかりやすくて，サンプルを考えましょう．サンプル1から要素を1つ増やしたものです．
5 6 1 3 2 6 4
このとき，6の約数は1, 2, 3, 6であり，1の個数は1個，2の個数は2個，3の個数は1個，6の個数は1個です．1の個数と6の個数をかけるとを含むペアは1通りです（1と6）．2の個数と3の個数をかけると，
を含むペアは2通りです（3と2，3と4）．1の個数と4の個数をかけると
を含むペアは1通りです（1と4）．
を含むペアは1通りです（2と6）．
を含むペアと，
を含むペアというのは区別します3．
これに対し，と
をかけて
の約数になるようなペアだけ数え上げればいいです．具体的には，約数を二重ループで回して，順番を気にせずにかけて
の約数になるなら和を取ってしまいます．そうすると
を含むペアと
を含むペアが同じなので，最終的な和は答えより2倍大きい値になります．ちょうど2倍になっているので2で割ってあげると求めたい答えが得られます．
ただし，一つ注意する点があります．6の個数と6の個数をかけるとを含むペアの総数が得られるとしたいですが，同じものを2つ選んだペアも数え上げてしまっているので，答えが正しいものより大きくなってしまします（実際，上のサンプルでは6の個数は1個でペアはできないのに，
を含むペアを一つ数えてあげてしまうことになります）．これを避けるために，
と
が同じものだったときは，
を足してあげればいいです．これは
という集合から2つ選ぶという組合せの総数と考えることができます4．
提出コード
提出コード
from math import gcd
import sys
input = sys.stdin.buffer.readline
def main():
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
def enum_divisors(n):
# 約数列挙
divs = []
for i in range(1, n+1):
if i*i > n:
break
if n % i == 0:
divs.append(i)
if n//i != i:
# i が平方数でない
divs.append(n//i)
return divs
divs = enum_divisors(K)
G = [gcd(a, K) for a in A]
B = {d: 0 for d in divs}
for g in G:
B[g] += 1
ans = 0
for g in divs:
for rg in divs:
if (g*rg) % K == 0:
ans += B[g] * (B[rg] - (g == rg))
print(ans//2)
if __name__ == '__main__':
main()
僕はこの問題を解説ACしたのですが，解説pdfを読んでも全然わからなかったのでTwitterで質問しまくりました．はてぃーぽったーさん，茶碗蒸しさんありがとうございます．
