Boj 8222 Distance

https://www.acmicpc.net/problem/8222

정수론 문제입니다..

전 정수론 문제를 좋아하지 않지만 한 번씩 풀어줘야 감을 잃지 않기 때문에 풀어봤습니다.

 

일단 이 문제는 정수론보단 구현에서 더 애를 먹었습니다.... ( 제가 구현을 진짜진짜진짜 못해서... )

 

문제 요약을 하자면

 

배열 $ 1 <= i < = N $ 인 $ i $ 번째 값을 $ A $ 라고 하고 $ 1 <= j <= N $ $ and $ $ i \neq  j $ 인 $ j $ 번째 값을 $ B $ 라고 합시다

그리고 $ Prime(x) $ 를  $ x $ 가 가진 중복을 허용한 소수의 개수라고 정의하겠습니다 ( 예를 들어 4 인 경우는 2 가 두개니깐 $ Prime(4) $ 는 2 입니다. )

$ Prime(A) + Prime(B) - 2 * Prime(gcd(A,B)) $ 를 최소화 하는 값 중 $ j $ 가 최소를 각 $ i $ 마다 구하는 겁니다.

 

그냥 naive 하게 값을 구하면 $ N^{2} * \ sqrt{1e6}  $ 이 될 겁니다.

어떻게 하면 $ N * \ sqrt{1e6}  $ 으로 줄일 수 있을 까요?

 

첫 번째로 dp 배열을 만듭니다.

 

$ dp[x][0][0] $ 는 $ x $ 를 소인수로 가지는 배열에서의 어떤 값을 $ A $ 라고 할 때 $ Prime(A) $ 최소값이고

$ dp[x][0][1] $ 는 그 값을 가진 $ A $ 의 위치 입니다.

$ dp[x][1][0] $ 는 위에서 $ Prime(A) $ 보다 작거나 $ Prime(A) $ 랑 같지만  $ A $ 의 위치가 더 큰 값을 저장합니다.

 

2개를 저장하는 이유는 $ i $ 번째에서 $ j $ 번째 값을 참조할 때 $ i \neq j $ 해야 됨으로 2개를 저장합니다.

 

그런 다음 각각 $ 1 <= i <= N $ 를 돌면서 $ arr[i] $ 와 나눠떨어지는 수를 $ A $ 라고 할 때

$ Prime(arr[i]) + Prime(dp[A][x][0]) - 2 * Prime(A) $ 가 최소가 되면서 $ dp[A][x][1] $ 도 최소가 되는 값을 찾아주면 됩니다.