[난이도 : F**K] 공약수

링크 : https://www.acmicpc.net/problem/1792

문제 : 

  세 개의 정수 a, b, d가 주어지면, 다음의 세 조건을 만족하는 자연수 순서쌍 (x, y)의 개수를 구하는 프로그램을 작성하시오.

    ① 1 <= x <= a

    ② 1 <= y <= b

    ③ x와 y의 최대공약수는 d이다.

입력 :

테스트케이스 n 이 들어오고

한 줄에 하나씩 테스트케이스에 해당하는 입력이 들어온다.

각 케이스마다 위에 정의된 a,b,d 이 차례로 들어온다.

입력으로 들어오는 숫자는 모두 50,000 을 넘지 않는다.

출력

위에 정의된 조건을 만족하는 순서쌍 (x,y)의 개수를 출력한다.

풀이:

일단 입력으로 들어오는 수 중 d는 훼이크임을 파악할 수 있다.

주어진 문제의 정답 = (1~(n/d)) 와 (1~(m/d)) 사이의 수 중 서로소인 수의 가지수

로 완벽하게 1:1 대응이 되기 때문이다.

쨌단 이제 서로소인 쌍의 수를 구하는 문제가 되었다.

문제 자체의 정답을 구하는 법은 간단하다.

n = a/d, m = b/d (여기서 나누기는 int형 기본 나눗셈.. 즉 소숫점을 버리는 나누기 연산을 뜻함) 으로 새로운 수 n,m을 정의하고

res = [n/1][m/1] - [n/2][m/2] - [n/3][m/3] + [n/6][m/6] - [n/5][m/5] + ...

뭐 이렇게 포함배제의 원리를 적절히 응용해서 수식을 전개하면

정답은 위와같은 꼴의 식이 나온다.

저 수식이 나온 과정은 간단하다.

1과 서로소인 개수 -> [m/1]

2와 서로소인 개수 -> [m/1] - [m/2]

3과 서로소인 개수 -> [m/1]           - [m/3]

...

a와 서로소인 개수 -> [m/1] - [m/(a의 소인수를 홀수개 곱한거)] + [m/(a의 소인수를 짝수개 곱한거)]

각 개수는 포함배제로 간단하게 구해지고, 우리가 원하는 답은 오른쪽 값들의 합이다.

여기서 [m/2] 가 나오는 횟수, [m/6]이 나오는 횟수 등의 규칙을 잘 관할해보면

[m/2]는 [n/2]번, [m/6]은 [n/6]번 등장함을 알 수 있고 이로인해 맨 처음 식

res = [n/1][m/1] - [n/2][m/2] - [n/3][m/3] + [n/6][m/6] - [n/5][m/5] + ...

가 나오게 된다.

그럼 이걸 이용해서 답을 구하면 되지 않을까?

n,m의 숫자 범위가 50,000 이고, 실제로 이 사이에 있는 (소인수의 차수가 1 또는 0인, 그러니까 포함배제원리 수식에서 "분모가" 될 수 있는 수)의 개수는 30401 개이다.

따라서 각 경우에 대해 답을 구하는데 걸리는 시간은 최대 O(30401) 이 걸리게 될 것이다.

이렇게 해서 구하면 너는 틀렸다.

왜냐하면 테스트케이스의 수가 50,000이기 때문이다!

이 사실 때문에 난이도가 중~하 에서 F**K으로 급상승하게 된다.

---

자 일단 진정하고... 

결론부터 말하면 내가 이 문제를 푸는데 사용한 일련의 과정들은 전부 다 "찍어서 알아낸 풀이"이다. 

일단 찍지 않고 사용한 개념을 소개하자

1. 뫼비우스 함수 (이하 meb(x) 로 표시)

meb(x) = x가 1일 때 1 

x를 소인수분해 했을 때 .소수의 차수가 2 이상인 소수가 있으면 0

x를 소인수분해 했을 때 .소수의 차수가 모두 1 이하인 경우 (-1) ^ (소인수의 개수)

뫼비우스함수는 위와같이 정의되는.. 참 뭐같은 함수이다. 이걸 어디다가 쓰지? 라는 의문이 들 정도로 말이다...

그래도 이 정의를 이용하면 위의 포함배제원리를 이용해서 구한 수식이 깔끔해진다.

res = sigma (i=1~n) [n/i][m/i] * meb(i);

여담으로 이 뫼비우스 함수의 한가지 재미있는 특징은

if n> 1, meb(n) = sigma {d|n} meb(d) = 0 이라는 점이다. n의 모든 약수들에 대해 그 약수의 meb값들을 더하면 항상 0이 나온다는 뜻. 뭐, 이 문제에서 사용될거같진 않다.

2. 뫼비우스 반전 공식

 위키 링크 참조 : http://ko.wikipedia.org/wiki/%EB%AB%BC%EB%B9%84%EC%9A%B0%EC%8A%A4_%EB%B0%98%EC%A0%84_%EA%B3%B5%EC%8B%9D

이건 직접 글 쓰는거보다 위키글을 참조하는게 200배 쉬울거같다ㅋㅋㅋㅋㅋ

자 위의 위키에 적힌 내용을 숙지했는가? 위키에서 사용된 저 식을 어떻게든 이용해먹을 준비를 해보자.

여기서 난 f 함수와 g 함수를 다음과 같이 정의했다

f(x) = [m/x] * meb(x)

g(x) = 1<= y <= m 중 x와 서로수인 y의 개수

보면 알겠지만 g(x) = sigma {d|n} f(d) 는 포함배제 수식과 똑같고, 따라서

우리가 답으로 구하고자 하는 수는 g(1) + g(2) + ... + g(n) 이 됨을 알 수 있다.

(n,m은 입력으로 구한 수)

이제 저 뫼비우스 반전 공식을 쓰면

g(x) = sigma {d|n} f(d)

f(x) = sigma {d|n} g(d) * meb(n/d);

이 됨을 알 수 있다.

이걸 어따쓰냐고? 그건 다음에 계속... 게시글 작성시간이 새벽 6시다..ㄷㄷㄷ잠이온다..하ㅏㅎ

---

엄청난 스포일러를 하나 하자면,

(아직 쓰지 않았지만) 위에 추가할 내용들을 읽고

res = [n/1][m/1] - [n/2][m/2] - [n/3][m/3] + [n/6][m/6] - [n/5][m/5] + ...

이 수식을 다시한번 쳐다보면

이 수식만으로 답을 구할 수 있음을 알 수 있다

즉, 내가 뫼비우스 반전공식을 써가며, 그리고 풀이의 규칙을 유추해가면서 쓴 풀이는

삽질이라는 것이다.

.............

위에서 [n/1] + [n/2] + ... + [n/k] 를 sqrt(n) 만에 구하는 방법에 대해 서술한 적이 있다.

이 시간복잡도의 주요 아이디어는

k <= sqrt(n) 인 경우 [n/k] 들은 서로 다 값이 다르고

k >= sqrt(n) 인 경우 [n/k] 결과값이 1 에서 sqrt(n) 사이의 값으로 결정된다는 점을 이용해서

k <= sqrt(n)일 때 , k >= sqrt(n) 각 경우에 대한 [n/k] 값의 합을 구하면 된다.

그럼 여기서도 비슷한 방식을 채용해보자.

k <= sqrt(n) || k <= sqrt(m) 인 경우 [n/k]*[m/k] 는 서로 다 값이 다르고

k >= sqrt(n) && k>=sqrt(m) 인 경우

[n/k][m/k] 값이 서로 같은  k의 구간을 구할 수 잇다. [n/k][m/k]는 최대 2*(sqrt(n)+sqrt(m)) 가지의 값을 가진다.

즉 [n/k][m/k] 값을 결정하는 구간의 개수는 sqrt(n) * 3 정도라는 것.

sqrt(n)만에 답을 구할 수 있게 되었다.

k의 세세한 범위는 예제 데이터 돌려보면서 테스트 해보시길ㅋㅋㅋㅋ

....하하 문제가 훨씬 간단해지지 않았는가....

아오 이런 풀이는 좀 빨리 떠오르라고ㅋㅋㅋㅋㅋ

이 풀이를 알고나서 뫼비우스 반전공식으로 푸는 방법을 적을 의욕이 사라졌다.

에라이 ㅋㅋㅋ