BOJ 27343 - Bomboni

Lemma

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

Proof

kpk \mid pkqk \mid q 라면 자명하다.

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

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

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

SolutionPermalink

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

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

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

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

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

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

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

Tags:

Categories:

Updated:

Comments