제퍼디! 회문 소수 카테고리

시간 제한1초메모리 제한128 MB

요약
주어진 진법에서 n자리이면서 회문 소수이고 2^31 미만인 수의 개수를 구한다. 0 0이 나올 때까지 자릿수와 진법 쌍을 읽는다.
난이도

보통10점 중 5점

유형
정수론, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

어떤 수가 1보다 크고 1과 자기 자신으로만 나누어떨어지면 그 수를 소수(prime)라고 한다. 정의에 따라 0과 1은 소수가 아니다.

회문 수(palindromic number)란 그 표기를 앞에서 읽으나 뒤에서 읽으나 똑같은 문자열이 되는 수를 말한다.

당신은 "회문 소수" 카테고리의 문제를 준비하는 출제팀의 일원으로서, 제퍼디! 형식의 답과 그에 대응하는 질문을 생성하는 프로그램을 작성한다.

자릿수 nn과 진법 bb가 주어지면, bb진법으로 표기했을 때 회문이면서 동시에 소수이고 그 값이 2312^{31} 미만인 nn자리 수가 몇 개인지 센다. nn자리 수에는 선행 0이 없으므로 가장 앞자리 숫자는 0이 아니다.

입력

입력은 공백으로 구분된 여러 개의 수 쌍으로 이루어지며, 두 개의 0으로 이루어진 쌍으로 끝난다. 각 쌍에서 첫 번째 수는 고려할 자릿수 nn이고, 두 번째 수는 수를 표기할 진법 bb이다.

이 문제에서 세는 모든 회문 소수는 부호 있는 32비트 정수 범위 안에 들어간다(즉 값이 2312^{31} 미만이다).

진법 bb는 2 이상 36 이하의 정수이다. 10보다 큰 진법은 16진법을 확장한 방식으로 다루며, 사용할 수 있는 숫자는 ['0'..'9']와 ['a'..'z']이다.

출력

각 쌍마다 두 줄을 출력한다. 첫 줄은 자릿수와 진법을 나타내는 (제퍼디! 형식의) "답"이고, 둘째 줄은 찾은 회문 소수의 개수를 나타내는 "질문"이다. 연속한 두 쌍 사이는 빈 줄 하나로 구분한다.

n, b, count를 각각의 값으로 바꾸어 정확히 다음 형식으로 출력한다:

The number of n-digit palindromic primes < 2^31 in base b.
What is count?

예제4

  1. 예제 1

    입력
    1 10
2 10
3 10
4 24
5 4
0 0
    예상 출력
    The number of 1-digit palindromic primes < 2^31 in base 10.
What is 4?

The number of 2-digit palindromic primes < 2^31 in base 10.
What is 1?

The number of 3-digit palindromic primes < 2^31 in base 10.
What is 15?

The number of 4-digit palindromic primes < 2^31 in base 24.
What is 0?

The number of 5-digit palindromic primes < 2^31 in base 4.
What is 10?

  2. 예제 2

    입력
    1 10
0 0
    예상 출력
    The number of 1-digit palindromic primes < 2^31 in base 10.
What is 4?

  3. 예제 3

    입력
    1 2
2 2
3 2
0 0
    예상 출력
    The number of 1-digit palindromic primes < 2^31 in base 2.
What is 0?

The number of 2-digit palindromic primes < 2^31 in base 2.
What is 1?

The number of 3-digit palindromic primes < 2^31 in base 2.
What is 2?

  4. 예제 4

    입력
    1 3
2 3
3 3
4 3
5 3
0 0
    예상 출력
    The number of 1-digit palindromic primes < 2^31 in base 3.
What is 1?

The number of 2-digit palindromic primes < 2^31 in base 3.
What is 0?

The number of 3-digit palindromic primes < 2^31 in base 3.
What is 2?

The number of 4-digit palindromic primes < 2^31 in base 3.
What is 0?

The number of 5-digit palindromic primes < 2^31 in base 3.
What is 3?