Sunday, January 4, 2015

Polish Olympiad in Informatics 2006/2007 Stage 1 - 'Queries'

Problem Link(문제 링크)

문제 요약 : 1 ≤ x ≤ a이고 1 ≤ y ≤ b일 때, gcd(x, y) = d인 (x, y) 쌍의 개수를 구하시오.

gcd(x, y) = d이므로 x = pd, y = qd라고 하면, 1 ≤ p ≤ a/d이고 1 ≤ q ≤ b/d일 때 (p, q) = 1인 쌍의 개수를 구하는 것과 동치가 된다.(㉠)

가장 먼저 생각할 수 있는 것은 O(ab log x)로서 모든 (p, q) 쌍에 대해 gcd 테스트를 해보는 것이다.

여기서 조금 더 개선하면, 오일러 파이 함수를 써서 하나의 p에 대해서 모든 q에 대해 gcd 테스트를 하지 않을 수 있다. 0~(p-1)까지의 패턴이 반복되므로 q에 걸쳐있는 마지막 패턴에 대해서만 유효한 범위에 대해 gcd 테스를 해볼 수 있다. 시간복잡도에는 큰 변화가 없다.

다르게 생각해보면 gcd(p, q) = 1인 걸 다 구하는 것이 아니라, gcd(p, q) = k인 걸 빼보는 방법을 떠올리 게 된다. 위에서 썼던 ㉠ 방법을 쓰고, 포함배제를 쓰면 O(a log b) 정도에 구할 수 있다.

좀 더 생각하고 관찰해보면 f(p, q) = f(p/2, q/2) + f(p/3, q/3) - f(p/6, q/6) + f(p/5, q/5) + f(p/7, q/7) - f(p/10, q/10) ... 이 되는 걸 알 수 있다. 즉, f(p, q) = 시그마{ f(p/i, q/i) } * 뫼비우스 함수(i)가 되는 것이다.

여기서 뫼비우스 함수는 곱의 함수이므로 약수 구하듯이 해서 n루트n의 시간복잡도에 구할 수 있고, 저 시그마 부분을 빠르게 개선해야한다.

p/i나 q/i 값이 변하게 되는 i 중 최솟값으로 자꾸 갱신시켜주면, 그 갱신이 3*루트(a)번 정도가 됨을 알 수 있다.

따라서 O(쿼리 수 * 루트 a)의 시간복잡도에 문제가 해결된다.

No comments:

Post a Comment