[BOJ 1335] 여섯 쌍 서로소

구해야 하는 것은

\[\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[ \gcd(Y_{a,b},Y_{c,d},Y_{e,f})=1]\]

이다. 뫼비우스 역변환을 이용하면

\[\sum_{s=1}^{359999}\mu(s)\sum_{(a,b)}\sum_{(c,d)}\sum_{(e,f)}[s|Y_{a,b}][s|Y_{c,d}][s|Y_{e,f}]\]

이다. 그럼 우리는 $Y_{a,b}$이 각각 어떤 값을 가지고 얼마나 많은 중복이 일어나는지 세면 답을 구할 수 있다.

문제에서 $Y_{a,b}=X_{a}\times X_{b}\pmod{359999}$이다. 즉, $X_{a}$들의 범위는 $0~359998$이라 생각해도 무방하다. 특히, $359999 = 599 \times 601$로 CRT를 이용하여 $X_{a}$를 쌍 $(i,j)$로 대응시킬 수 있고 $i \equiv X_{a}\pmod{599}$ 그리고 $j\equiv X_{a}\pmod{601}$이다. 주의할 점은 최대공약수가 $0$에 대해서도 사용된다는 것이다. 우리가 가장 처음에 유도한 식에서는 $Y_{a,b}$가 $0$인 경우가 포함되어있지 않아 직접 개수를 세어 줘야 한다.

 

Case 1: $Y_{a,b}=0$

이 가능성은 다음의 세부 케이스들로 나뉘어진다. $i,j$가 0이 아니라고 하자.

• $(0,0) \times (i,j)$

$X_{i}$들 중 $(0,0)$인 수들의 개수가 $x$개 라고 하자. 주어진 $X_{i}$들의 개수가 $N$개 일 때 위 케이스는 총 $2Nx-x^{2}$번 나타난다.

• $(i,0) \times (0,j)$

각 쌍이 의미하는 것은 결국 $599$의 배수와 $601$의 배수들의 곱이다. $599$의 배수의 개수를 $y$, $601$의 배수의 개수를 $z$라고 한다면 이 케이스는 $2yz$번 나타난다.

 

Case 2: $Y_{a,b}\ne 0$

다음 세부 케이스들을 고려하자. $i,j,k,l$가 0이 아니라고 하자.

• $(0,i)\times (0,j)$
• $(i,0)\times (j,0)$
• $(0,i)\times (j,k)$
• $(i,0)\times (j,k)$

위 4가지 케이스들은 서로 겹치지 않고 그 결과가 $(i,0)$ 또는 $(0,j)$ 꼴 이라는 성질을 가진다. 따라서 위 경우들은 Naive하게 $O(359999)$로 구할 수 있다. 

• $(i,j)\times (k,l)$

이 경우 우리는 이산 로그를 이용한다. 공교롭게도 $599, 601$은 $7$을 원시근으로 갖는다. 적절한 테이블을 만들어 $1~598$, $1~600$까지 각각의 이산 로그를 계산하자. $7^{p}\equiv i\pmod{599}$, $7^{r}\equiv k\pmod{599}$, $7^{q}\equiv j\pmod{601}$, $7^{s}\equiv l\pmod{601}$을 만족한다고 하면, $(i,j)\times (k,l)=(7^{p+r},7^{q+s})$가 되는 것이다. 덧셈에 관한 것이므로 FFT를 이용하는 방법을 생각할 수 있다. 다항식 $p$에서 $x^{p\times 1200 + q}$의 계수를 쌍 $(i,j)$의 개수로 두자. 그럼 $p^{2}$은 두 쌍의 가능한 모든 조합들을 저장하게 된다. 게다가, $(p\times 1200 + q)+(r\times 1200 + s)=(p+r)\times 1200+(q+s)$이고 $q+s<1200$이다. 따라서 우리는 모든 조합들을 식별해낼 수 있다.  다항식 $p$의 최대 degree는 $720000$로 FFT의 시간복잡도 $O(n\log n)$을 생각해보면 충분히 시간 내에 들어온다는 것을 확인할 수 있다. 

 

이렇게 모든 경우의 수를 구했다. 남은 것은 주어진 summation을 계산하는 것인데 우리가 확인해야 할 것은 결국 $s$의 배수들의 개수이다. 구한 $Y_{a,b}$의 범위가 $0$과 $359999$ 사이라는 것을 감안했을 때, 우리가 실제로 연산해야 하는 횟수는 $O(359999\log 359999)$이다. 또, 다음 케이스를 잊으면 안된다. $\gcd(0,0,1)$ 그리고 $\gcd(0,a,b)=1$ 인 경우. 

첫 경우는 단순 곱셈으로 해결되며 두 번째 경우는 $\gcd(a,b)=1$이 되는 케이스를 찾아주면 된다. summation이 3개에서 2개로 줄어들었다고 생각하면 된다.