ディスカバリーチャンネルコードコンテスト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; }