교대

$A$와 $B$의 각 자릿수를 $100$진수의 한 자리처럼 해석하자. 어떤 양의 정수 $X$의 자릿수가 $x_1,x_2,\ldots,x_k$라면

$$v(X)=x_1\cdot 100^{k-1}+x_2\cdot 100^{k-2}+\cdots+x_k$$

로 정의한다. 앞에 $0$을 붙여도 이 값은 변하지 않는다.

그러면 항상

$$A \star B = 10v(A)+v(B)$$

이다. 따라서 필요한 조건은

$$10v(A)+v(B)\equiv 0 \pmod P$$

이다.

먼저 $v(B) \bmod P$를 왼쪽부터 한 자리씩 보며 계산한다. $P=2$ 또는 $P=5$라면 $10v(A)$는 항상 $P$의 배수이므로, $v(B)\equiv 0 \pmod P$일 때에만 답이 존재한다. 이 경우 최소 양의 정수는 $1$이고, 그렇지 않으면 답은 $-1$이다.

이제 $P$가 $2,5$가 아닌 경우를 보자. $P$는 소수이므로 $10$의 역원이 존재한다. 따라서 $v(A)$가 가져야 하는 나머지는

$$\mathrm{target}\equiv -v(B)\cdot 10^{-1}\pmod P$$

로 하나로 정해진다.

이제 $v(A)\equiv \mathrm{target}\pmod P$를 만족하는 최소 양의 정수 $A$를 찾으면 된다. 현재 나머지가 $r$이고 새 십진수 자릿수 $x$를 뒤에 붙이면 새로운 나머지는

$$(100r+x)\bmod P$$

이다.

나머지 $0,1,\ldots,P-1$을 정점으로 두고 BFS를 수행한다. 시작 정점은 한 자리 수 $1,2,\ldots,9$가 만드는 나머지이며, 각 정점에서는 자릿수 $0,1,\ldots,9$를 붙이는 전이를 사용한다. 시작 자릿수와 전이 자릿수를 오름차순으로 처리하면 BFS에서 처음으로 목표 나머지에 도달했을 때의 문자열이 곧 최소 양의 정수이다.

정점 수는 $P$개이고 각 정점에서 최대 $10$개의 전이를 확인하므로 시간 복잡도는 $O(P+|B|)$, 메모리 복잡도는 $O(P)$이다.

Solution written by GPT5.5