BOJ 26953 - 일차합동식

June 11, 2023

풀다 생각이 잘 안떠올랐는데 풀이도 없어 꽤나 곤란했던 문제

조금 느린 방법으로 풀 수 있었다.

아무리 생각해도 Phi 함수를 어떻게 쓸지 모르겠어서 그냥 포함 배제의 원리로 풀었다.

대략 풀이는 다음과 같다.

공통

$ax \equiv b \pmod m$ 이므로 $ax+my=b$ 이고 이 베주항등식의 해가 존재할 조건은 $gcd(a,m) \mid b$ 이다.

$m$을 순회하며 $m$의 약수 $d$에 대해 살핀다.

$gcd(a,m) = d$ 인 $a$의 개수를 세는 문제로 환원되고 이는 $gcd(a/d, m/d) = 1$ 과 동일하다.

따라서 $\left\lfloor M/d \right\rfloor$ 까지의 수 중 $m/d$ 와 서로소인 것의 개수를 세면 되고

이걸 포함 배제의 원리로 직접 구해서 풀었더니 느린 풀이로 통과되었다.

위에서의 관찰을 기반으로 $m$에 대해 순회하지말고 $b$의 약수 $d$에 대해 고려한다.

$gcd(a,m)=d \mid b$ 인 쌍 $(a,m)$을 센다.

이걸 세는 방법으로 오일러 피함수를 이용하는 것이다.

$gcd(a,m)=d \to gcd(a/d, m/d) = 1$ 이 된다.

$1 \to m/d$ 까지의 모든 $i$ 에 대해 $\phi(i)$ 를 보자. 결국 $\phi(i)$이 $(j, i), j \le i$ 인 서로소인 쌍의 개수이다.

따라서 $\displaystyle 2\sum_{i=1}^{M/d} \phi(i)-1$ 를 정답에 더해준다.

$2$를 곱해준 이유는 $a, m$ 의 순서가 바뀔 수 있기 때문이고, $-1$ 을 해준 이유는 $1$만 특별하게 $(1,1)$로 동일한 수로 $\phi$함수에서 세지기 때문이다.

마지막으로 정답에 $-M$ 을 해주는데 $2 \le M$ 이고 $M=1$ 일 땐 $a$가 뭐든 항상 해가 존재하기 때문이다.

시간복잡도는 $O(M)$ 이다.

두 자연수 범위에서 서로소인 쌍의 개수를 세는건 나중에 블로그에 다시 정리하겠지만 뫼비우스함수를 이용해 푸는 대표적인 문제이다.

$\mu(i)$는 $i$가 square free수면 $0$ 이고 아니면 $(-1)^{\vert p \vert}$ 인 함수이다.

$\vert p \vert=\text{서로 다른 소인수의 개수}$