DDCC2016予選 C - ロト2 (400)

C - ロト2

概要

N項の数列Aと正整数Kが与えられる。
Ai * AjがKの倍数であるような(i, j) (i < j)の組はいくつあるかを求めよ。
（以降、aがbの倍数である、すなわちbがaを割り切ることをb | aと記載する）

制約

1 ≦ N ≦ 200000
1 ≦ Ai ≦ 10^9
1 ≦ K ≦ 10^9

方針

まず考えられるのはすべての(i, j) (i < j)の組み合わせに対しK | Ai * Ajであればカウントする、という方法だが、これはO(N^2)であるため間に合わない。

実は、K | x * y ⇔ K | gcd(x, K) * gcd(y, K)である。
つまりK が x * y を割り切るかどうかは、Kが「xとyについてそれぞれKと最大公約数をとったものの積」を割り切るかどうかを確認すればよい。
こうすると、各AiをKとの最大公約数ごとにグルーピングすることができ、探索範囲を狭めることができる。

なお、K | x * y ⇔ K | gcd(x, K) * gcd(y, K) は公式解説に証明がある。
素因数分解したときの指数を考えることでも理解することができる。すごくざっくりいうと下記の通り

• gcd(a, b)はaとbをそれぞれ素因数分解し、各素数の指数についてa, bとでより小さいほうの指数を採用してゆく操作
• a | bはaの各素数の指数がbの指数以下であるとき成り立つ
• K | x * yを考えるときは、Kの各素数の指数について、その指数より大きい部分を考える必要はないので、gcd(x, K)・gcd(y, K)してその部分をそぎ落とす

解答

https://atcoder.jp/contests/ddcc2016-qual/submissions/4660878

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a % b);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N, K;
	cin >> N >> K;
 
	ll A[N];
	rep(i, N) cin >> A[i];
 
	map<int, ll> mp;
	vector<ll> v;
	rep(i, N){
		ll x = gcd(A[i], K);
		// cout << A[i] << "," << x << endl;
		auto it = mp.find(x);
		if(it == mp.end()){
			v.push_back(x);
			mp[x] = 0;
		}
		mp[x]++;
	}
 
	ll ans = 0;
	int m = v.size();
 
	for(int i = 0; i < m; i++){
		if(v[i] * v[i] % K == 0){
			ans += mp[v[i]] * (mp[v[i]] - 1) / 2;
		}
 
		for(int j = i+1; j < m; j++){
			if(v[i] * v[j] % K == 0){
				ans += mp[v[i]] * mp[v[j]];
			}
		}
	}
 
	cout << ans << endl;
}