[BOJ 16709] Congruence Equation

$a,b$ 둘 다 $p$의 배수라고 하면 자명하게 성립하므로 $(p-1)^{2}$개를 일단 찾았다. $a$나 $b$ 중에 1개만 modulo $p$로 0이라고 하자. 일반성을 잃지 않고 $b\equiv 0\pmod{p}$라고 한다면 $a^{b}\equiv 0\pmod{p}$이며 $p|a$이고 모순이다. 따라서 우리는 $a,b$ 둘다 $p$의 배수가 아닌 경우를 고려한다. 그럼 원시근 $g$에 대하여 $a\equiv g^{x}\pmod{p}$, $b\equiv g^{y}\pmod{p}$라고 대응시길 수 있고 $0\le x,y \le p-2$이다. 주어진 식을 다시 써보면 $xb\equiv ya\pmod{p-1}$이다. 

우리가 $xb\equiv ya\pmod{p-1}$를 만족시키는 $a,b,x,y \pmod{p-1}$ 튜플을 찾았다고 하자. 그럼 $a\equiv t\pmod{p}$, $b\equiv s\pmod{p}$라고 하면 CRT에 의해 유일한 해 $a,b\pmod{p(p-1)}$이 존재한다. 문제에서 주어진 범위를 고려하면 그 범위 내에서는 쌍 $(a,b)$가 유일하다. 따라서 우리는 $xb\equiv ya\pmod{p-1}$를 만족하는 튜플 $(a,b,x,y)$의 개수가 $a^{b}\equiv b^{a}\pmod{p}$를 만족하는 쌍 $(a,b)$의 개수와 일치함을 알아냈다. 

튜플의 개수를 구하기 위해서 먼저 $1\le a,x \le p-1$를 fix해보자. $u=\gcd(a,p-1)$라고 두고 $y$의 개수를 세보면, $u|bx$인 경우 $u$개가 가능하다. 또, $bx\equiv 0\pmod{u}$인 $b$의 개수는 $\gcd(u,x)$개가 $0\le b\le u$인 경우 존재한다. 따라서 $1\le b\le (p-1)$의 볌위에서는 $\frac{p-1}{u}\gcd(u,x)$. 따라서 $(b,y)$의 개수는 두 개수의 곱인 $(p-1)\gcd(u,x)$가 된다. $\gcd(a,p-1)=u$가 되는 $a$의 개수는 $\phi((p-1)/u)$이므로 우리가 계산하는 값은 

\[(p-1)\sum_{x=1}^{p-1}\sum_{a=1}^{p-1}\gcd(a,p-1,x)=(p-1)\sum_{x=1}^{p-1}\sum_{u|p-1}\phi(\frac{p-1}{u})\gcd(u,x)\cdots (1)\]

이다. $\gcd(u,x)=d$인 $1\le x\le u$의 개수는 $\gcd(u/d,x/d)=1$을 만족하는 $x/d$의 개수와 같고, 이 값은 $\phi(u/d)$이다. 

그럼 $1\le x\le p-1$이고 $\gcd(u,x)=d$를 만족하는 $x$의 개수는 $\frac{p-1}{u}\phi(u/d)$이고 다음을 얻는다. 

\[(1)=(p-1)\sum_{u|p-1} \phi(\frac{p-1}{u}) \sum_{d|u}\frac{p-1}{u}d\ \phi(u/d)\]

$u$ 대신에 $\frac{p-1}{u}$를 대입하면

\[(p-1)\sum_{u|p-1}\phi(u)\sum_{ud|p-1}ud\ \phi(\frac{p-1}{ud})\]

$ud=k$라고 치환하면

\[(p-1)\sum_{k|p-1}k\phi(\frac{p-1}{k})\sum_{u|k}\phi(u)=(p-1)\sum_{k|p-1}k^{2}\phi(\frac{p-1}{k})\]

이제 $f(n)=\sum_{d|n}d^{2}\phi(n)$이라고 두자. 그럼 $f$는 multiplicative 하므로 prime power에 대해서만 계산해주면 된다. 소수 $p$와 자연수 $k$에 대하여 다음을 이용하자.

\[f(p^{k})=\sum_{i=0}^{k}p^{2i}\phi(p^{k-i})=p^{2k}+(p-1)\sum_{i=0}^{k-1}p^{k+i-1}=p^{2k}+p^{2k-1}-p^{k-1}\]

 

최종적으로 우리가 구해야 하는 값은

\[(p-1)^{2}+(p-1)f(p-1)\]

$p-1$을 pollard rho로 소인수 분해 하면 된다.