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

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

問題概略

N個の整数A1~ANが与えられる。i<jとなるAi,Ajを選んだ時、２つの積がKの倍数となる組み合わせを求めよ

制約

• 1≦N≦200,000
• 1≦A_i≦10⁹(1≦i≦N)
• 1≦K≦10⁹
• A_i, K はいずれも整数

解法

N^2では間に合わない。組み合わせ問題でよくあるまとめ上げを使う。

２つの積がKの倍数になる -> Kの約数でないものは考えなくていいため、Aたちの中からKの約数だけを取り出し、それぞれ何個あるかを持っておく。

あとは全探索。Kの約数は1000個程度しかない

問題の芯

組み合わせ問題は共通の状態でまとめ上げられないか考える

類題

D - 連結 / Connectivity

public static void main(String[] args)
    {
        N = sc.nextInt();
        K = sc.nextInt();
        A = sc.nextIntArray(N);
        HashMap<Long, Integer> divisors = new HashMap<>();
        for (int i = 0; i < N; i++)
        {
            long key = gcd(A[i], K);
            Integer num = divisors.get(key);
            divisors.put(key, num == null ? 1 : num + 1);
        }
        long res = 0;
        for (Map.Entry<Long, Integer> entry1 : divisors.entrySet())
        {
            for (Map.Entry<Long, Integer> entry2 : divisors.entrySet())
            {
                long k1 = entry1.getKey();
                long k2 = entry2.getKey();
                if (k1 * k2 % K != 0) continue;
                int v1 = entry1.getValue();
                int v2 = entry2.getValue();
                if (k1 == k2)
                {
                    res += (v1 * (long)(v2 - 1));
                }//
                else
                {
                    res += ((long)v1 * v2);
                }
            }
        }
        res/=2;
        System.out.println(res);
    }