BOJ 27343 - Bomboni

July 19, 2023

Lemma

$gcd(pq, k)=gcd(gcd(p,k) \cdot gcd(q,k), k)$ 이다.

Proof

$k \mid p$나 $k \mid q$ 라면 자명하다.

그렇지 않다고 하고 $p$와 $q$에 대해 각 약수들은 $gcd(d,k) = 1$ 인것과 $gcd(d,k) \neq 1$ 인 것으로 나뉜다.

좌변은 $pq$에서 $gcd(d, k) \neq 1$ 인 약수들의 곱만 취해도 $gcd(pq, k)$ 의 값에 영향을 미치지 않는다.

우변은 $gcd(p, k)$ 와 $gcd(q, k)$ 가 결국 $gcd(d, k) \neq 1$ 인 것들을 의미하므로 등식이 성립한다. $\square$

Solution

DP를 이용하면 된다. $10^6$ 이하의 수의 약수들은 최대 300개이기 때문이다.

$k$의 배수가 되어야 한다는 것은 경로의 수들의 곱이 $p$라하면 $gcd(p,k)=k$ 임을 의미한다.

위의 Lemma에 의해 모든 수들을 미리 $k$와 $gcd$해두어도 무관하다.

$dp[i][j][g]$ 를 $(i, j)$ 까지 왔을 때 $k$와 $gcd$한 것들의 곱이라고 하자.

$k$의 약수는 최대 $300$개이기 때문에 $O(300 \cdot n^2)$ 으로 해결한다.

구현은 조금 있는데, $300$개의 약수들에 대해 어떤 두 약수의 곱과 $k$ 와의 최대공약수를 미리 전처리해두고 transition에 이용하는 방식으로 해결할 수 있다.

현재 칸에서 $i$ 번째 약수와 그 다음칸이 $k$와 $gcd$한것과 곱해져서 어떤 약수값이 되어야 하는지를 미리 전처리하는 것이다.