BOJ 27343 - Bomboni
Lemma
gcd(pq,k)=gcd(gcd(p,k)⋅gcd(q,k),k) 이다.
Proof
k∣p나 k∣q 라면 자명하다.
그렇지 않다고 하고 p와 q에 대해 각 약수들은 gcd(d,k)=1 인것과 gcd(d,k)=1 인 것으로 나뉜다.
좌변은 pq에서 gcd(d,k)=1 인 약수들의 곱만 취해도 gcd(pq,k) 의 값에 영향을 미치지 않는다.
우변은 gcd(p,k) 와 gcd(q,k) 가 결국 gcd(d,k)=1 인 것들을 의미하므로 등식이 성립한다. □
Solution
DP를 이용하면 된다. 106 이하의 수의 약수들은 최대 300개이기 때문이다.
k의 배수가 되어야 한다는 것은 경로의 수들의 곱이 p라하면 gcd(p,k)=k 임을 의미한다.
위의 Lemma에 의해 모든 수들을 미리 k와 gcd해두어도 무관하다.
dp[i][j][g] 를 (i,j) 까지 왔을 때 k와 gcd한 것들의 곱이라고 하자.
k의 약수는 최대 300개이기 때문에 O(300⋅n2) 으로 해결한다.
구현은 조금 있는데, 300개의 약수들에 대해 어떤 두 약수의 곱과 k 와의 최대공약수를 미리 전처리해두고 transition에 이용하는 방식으로 해결할 수 있다.
현재 칸에서 i 번째 약수와 그 다음칸이 k와 gcd한것과 곱해져서 어떤 약수값이 되어야 하는지를 미리 전처리하는 것이다.
Comments