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

できなかったのでやり直し。

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

x * y が kの倍数 <=> gcd(x, k) * gcd(y, k) が kの倍数という性質を用いる。

計算量はO(N2) -> O(Kの約数の個数2)になる。

今回Kの約数は1344個らしい。

gcd(Ai, K)の値をmapに保存しておいて、Kの倍数になるか2重ループで調べる。 gcd(Ai, K) * gcd(Aj, K) % K == 0となる時、 map[gcd(Ai, K)] == map[gcd(Aj, K)] の時はmap[gcd(Ai, K)]個から2個選ぶ選び方の数、 そうでない時はmap[gcd(Ai, K)] * map[gcd(Aj, K)]。 ただし、二重ループで重複して数えてしまうので最後に2で割って足した 。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
//最大公約数
ll gcd(ll a, ll b) {
  while (a && b) {
    if (a >= b) a %= b;
    else b %= a;
  }
  return a + b;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, K; cin >> N >> K;
  map<ll, ll> MAP;
  FOR(i,0,N) {
    ll in; cin >> in;
    MAP[gcd(K, in)]++;
  }
  ll ans = 0;
  ll ans2 = 0;
  for(auto m1 : MAP) {
    for(auto m2 : MAP) {
      if((m1.first * m2.first) % K == 0) {
        if(m1.first != m2.first) {
          ans2 += m1.second * m2.second;
        } else {
          ans += m1.second * (m2.second - 1) / 2;
        }
      }
    }
  }
  cout << ans + ans2 / 2 << endl;
  return 0;
}