열 수 있는 자물쇠

이제 잠글 시간이다. 하지만... 자물쇠의 열쇠를 잃어버렸다.

공통 정수 $a > 1$을 공유하는 $N$개의 자물쇠가 있다. 각 자물쇠에는 고유한 정수 $b_i$이 대응된다. 열쇠는 양의 정수 쌍 $(x,y)$로 나타낼 수 있으며, $ya^x = b_i$을 만족하면 $b_i$인 자물쇠를 열 수 있다.

적어도 하나의 $b_i$에 대해 $ya^x = b_i$을 만족하는 가능한 모든 열쇠 $(x,y)$을 구하여라.

채점

제출한 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹은 여러 테스트 케이스로 구성된다. 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$22$| 모든 $1 \leq i \leq N$에 대해 $a, b_i \leq 100$이다.

$2$ |$33$| $a$은 소수이다.

$3$ |$45$| 추가 제한 조건이 없다.

첫째 줄에 자물쇠의 수와 공통 정수 $a$을 나타내는 두 정수 $N$과 $a$가 주어진다. ($1 \leq N \leq 2 \cdot 10^5$, $1 < a \leq 10^9$)

둘째 줄에 $N$개의 정수 $b_1, b_2, \dots, b_N$ $(1 \leq b_i \leq 10^9)$이 주어지며, $b_i$은 $i$번째 자물쇠를 나타내는 정수이다.

적어도 하나의 $i$ $(1\leq i \leq N)$에 대해 $ya^x = b_i$을 만족하는 양의 정수 쌍 $(x,y)$의 개수를 정수로 출력한다.