부호 처리 연습 (1) - Divisor Orthogonality

각 $i$에 대해 함수 $F_i(x)=i/x$를 생각하자. $A_{ij}=F_i(\gcd(i,j))$이다.

고정된 $i$에 대해, $d \mid i$인 $d$에 대해

$$h_i(d)=\sum_{e\mid d}\mu\left(\frac d e\right)\frac i e$$

로 정의한다. 뫼비우스 반전에 의해

$$\frac{i}{\gcd(i,j)}=\sum_{\substack{d\mid i\\d\mid j}}h_i(d)$$

가 성립한다.

따라서 $E_{dj}=[d\mid j]$, $H_{id}=h_i(d)$ if $d\mid i$, otherwise $0$로 두면 $A=HE$이다. 자연스러운 번호 순서에서 $E$는 대각 원소가 모두 $1$인 삼각행렬이고, $H$도 삼각행렬이다. 그러므로

$$\det(A)=\prod_{i=1}^{N}h_i(i)$$

이다.

이제

$$h_i(i)=\sum_{e\mid i}\mu\left(\frac i e\right)\frac i e =\sum_{r\mid i}\mu(r)r =\prod_{p\mid i}(1-p)$$

이다. 따라서 최종 답은

$$\prod_{i=1}^{N}\prod_{p\mid i}(1-p)$$

이고, 같은 소수 $p$가 기여하는 횟수는 $p$의 배수의 개수인 $\left\lfloor N/p\right\rfloor$번이다. 즉,

$$\det(A)=\prod_{p\leq N}(1-p)^{\lfloor N/p\rfloor}$$

이다.

에라토스테네스의 체 또는 선형 체로 $N$ 이하의 모든 소수를 찾고, 빠른 거듭제곱으로 위 식을 계산하면 된다. 시간복잡도는 $O(N+\pi(N)\log P)$이고, 메모리 사용량은 $O(N)$이다.

Solution written by GPT5.5