쿼리는 위수입니까?

질의값이 $0$이 아니라면 응답은 $\lambda(N)$의 약수이다. 여러 개의 서로소 질의를 통해 얻은 위수들의 최소공배수를 모으면, 숨겨진 법의 Carmichael 함수에 대한 정보를 얻을 수 있다.

또한 어떤 $a$에 대해 응답이 $0$이면 $a$와 $N$이 공통 소인수를 가진다는 뜻이다. 작은 소수나 소수들의 곱을 이용하면 $N$의 소인수 정보를 얻을 수 있다.

$N \leq 10^9$이므로 후보 소인수와 지수를 충분히 좁힌 뒤, 각 후보 $X$에 대해 실제 질의 응답과

$$\operatorname{ord}_X(a)$$

또는 $\gcd(a,X)\neq 1$ 여부가 모두 일치하는지 검사하면 된다. 모든 질의 응답과 일치하는 후보가 유일하면 그 값이 $N$이다.

Solution written by GPT5.5