First Digit One

Moderate

0/80

0 upvote

Problem statement

Ninja is exploring number base representations. He knows that for any integer N, its representation in base b is a sequence of digits dk d{k-1} ... d0 such that N = dk * b^k + ... + d0, where 0 <= di < b.

He wonders: for a given integer N, how many integer bases b (where b >= 2) exist such that the base-b representation of N starts with the digit 1?

For example, consider N = 6:

  In base 2: 6 = (110)_2. Starts with 1.
  In base 3: 6 = (20)_3. Does not start with 1.
  In base 4: 6 = (12)_4. Starts with 1.
  In base 5: 6 = (11)_5. Starts with 1.
  In base 6: 6 = (10)_6. Starts with 1.
For N=6, there are 4 such bases: 2, 4, 5, 6.

Your task is to find this count for any given N. If the number of such bases is infinite, you should report it.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer T, the number of test cases.

Each of the next T lines contains a single integer N.

Output Format:

For each test case, print a single line containing the number of bases b, or INFINITY if there are an infinite number of them.

Note:

An element from array 'a' and an element from array 'b' can be part of only one pair. Once used, they cannot be used again to form another pair.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

For N = 6:
  Bases where the representation has 2 digits (k=1): b^1 <= 6 < 2*b^1 \implies 3 < b <= 6. Bases are {4, 5, 6}. (Count = 3)
  Bases where the representation has 3 digits (k=2): b^2 <= 6 < 2*b^2 \implies \sqrt{3} < b <= \sqrt{6} \implies 1.73 < b <= 2.45. Base is {2}. (Count = 1)
  Total count = 3 + 1 = 4.
For N = 24:
  k=1: 12 < b <= 24. Bases {13, ..., 24}. Count = 12.
  k=2: \sqrt{12} < b <= \sqrt{24} \implies 3.46 < b <= 4.89.   Base is {4}. Count = 1.
  k=3: \sqrt[3]{12} < b <= \sqrt[3]{24} \implies 2.28 < b <= 2.88. No integer bases. Count = 0.
  k=4: \sqrt[4]{12} < b <= \sqrt[4]{24} \implies 1.86 < b <= 2.21. Base is {2}. Count = 1.
  Total count = 12 + 1 + 0 + 1 = 14.

Expected Time Complexity:

The expected time complexity is O(log N).

Constraints:

1 <= T <= 10^5
0 <= N < 10^12

Time limit: 1 sec

First Digit One

Console