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)의 시간복잡도에 문제가 해결된다.

Thursday, January 1, 2015

POJ 3468 - BIT를 이용해 구간에 값을 더하기

문제 : POJ(PKU) 3468 - A Simple Problem with Integers

열 A[1] A[2] ... A[N]이 주어졌을 때에, 연속된 부분 배열 A[i...j]에 x를 더하는 것과 A[i]+A[i+1]+...+A[j]를 묻는 쿼리 M개가 주어진다.

Binary Indexed Tree 2개를 이용해 O(N log N + M log n)에 해결가능하다.

y[i] = A[i]-A[i-1], z[i] = i*y[i]라고 정의하자.(A[0] = y[0] = z[0] = 0)

A[1]+A[2]+A[3]+A[4]

= y[1]+(y[2]+y[1])+(y[3]+y[2]+y[1])+(y[4]+y[3]+y[2]+y[1])

= 4*y[1] + 3*y[2] + 2*y[3] + y[4]

= 5*(y[1] + y[2] + y[3] + y[4]) - (y[1] + 2*y[2] + 3*y[3] + 4*y[4])

= 5*(y[1] + y[2] + y[3] + y[4]) - (z[1] + z[2] + z[3] + z[4])

일반화해보면

Sum(L, R) = A[L]+A[L+1]+...+A[R-1]+A[R]

= (R-L+1)*(y[L]+y[L+1]+...+y[R-1]+y[R]) - (z[L]+z[L+1]+...z[R-1]+z[R])

구간 A[i...j]에 x를 더하는 것은 i번째와 j+1번째의 y, z값만 변하므로 log N에 갱신 가능.

만약 j가 N이라면 j+1이 존재하지 않는 것에 유의하면 된다.

내 소스코드