Блог пользователя ZerocooL95

Question about palindromic numbers in other bases .
Автор ZerocooL95, история, 9 лет назад, По-английски

I was doing a problem on codechef and couldnt get to the solution . If anyone can help , it would be appreciated . Given a number N, write a program to compute the smallest base B such that N is palindromic when written in base B. 1<=N<=10**10. Link: https://www.codechef.com/problems/K2

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Suppose our palindrome has 3 or more digits, then B will be smaller than 1e5, so we can simply enumerate B and check if N is a palindrome.

When our palindrome has 2 digits, these 2 digits should be same, so there should be a x smaller than B, that x * B + x = N, x * (B + 1) = N. B + 1 should be a divisor of N. Then we can enumerate all divisors of N and update the answer.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi, as an extension, what would be the solution for this similar problem from the Canadian national olympiad? Essentially, the base can go up to 109 and all bases where the starting number X (in base-10) are a palindrome should be outputted?

    → Ответить