시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB555100.000%

문제

Nicholas Neverson was a student at Northlings Neverland Academy. As with any daydreaming student, Nicholas was playing around with a Kaleidoscope one day instead of paying attention to the teacher. Since this was math class, his daydreams quickly turned to palindromic numbers. A palindromic number is any number which reads the same forwards and backwards.

He describes his vision to you at lunch: numbers which are palindromic in several bases at once. Nicholas wonders how many such numbers exist. You decide you can quickly code up a program that given a range and a number k, outputs the number of numbers palindromic in all bases j, 2 ≤ j ≤ k, in that range.

입력

Input consists of three space-separated integers: a, b, and k. The input satisfies the following constraints:

  • 0 ≤ a ≤ b ≤ 2 000 000,
  • 2 ≤ k ≤ 100 000.

출력

Output the quantity of numbers between a and b inclusive which are palindromes in every base j, for 2 ≤ j ≤ k.

예제 입력 1

1 356 2

예제 출력 1

36

예제 입력 2

18 118 13

예제 출력 2

0

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2018 J번

  • 문제를 만든 사람: Alexander Scheel