Canadian Computing Olympiad 2025: Day 1, Problem 3

Since the CCO often uses integers, Alice needs to learn about the integers! A positive integer ~n~ can be written in base ~b~ as the sequence ~d_{m-1} d_{m-2} \dots d_1 d_0~ if the following hold:

• Each digit ~d_i~ is between ~0~ and ~b-1~, inclusive.

• ~d_{m-1} > 0~.

• ~n = d_{m-1} \times b^{m-1} + d_{m-2} \times b^{m-2} + \dots + d_1 \times b^1 + d_0 \times b^0~.

For example, the integer ~2025~ in base ~19~ is the sequence ~(5, 11, 11)~ because ~2025 = 5 \times 19^2 + 11 \times 19^1 + 11 \times 19^0~.

An integer ~n~ is ~b~-balanced if, when ~n~ is written in base ~b~, the average of the digits is ~\dfrac{b-1}{2}~. For example, ~2025~ is ~19~-balanced because ~\dfrac{5+11+11}{3} = 9 = \dfrac{19-1}{2}~.

Alice can easily find integers that are ~19~-balanced. However, she has trouble finding integers that are balanced in multiple ways. Given ~B~ and ~N~, please help Alice find the minimum integer ~x~ such that:

• ~x~ is ~b~-balanced, for all ~2 \le b \le B~.

• ~x \ge N~.

Input Specification

The first line of input contains two space-separated integers ~B~ and ~N~ ~(N \ge 1)~.

It is guaranteed that the answer does not exceed ~10^{18}~.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~B~	Bounds on ~N~
2 marks	~2 \le B \le 7~	~1 \le N \le 10^4~
6 marks	~2 \le B \le 6~	~N = 10^{10}~
2 marks	~2 \le B \le 7~	None
9 marks	~8 \le B \le 11~	~N = 1~
4 marks	~B = 8~	None
2 marks	~9 \le B \le 11~	None

Output Specification

Output the minimum integer ~x~ from the problem statement.

Sample Input 1

4 100

Output for Sample Input 1

141

Explanation for Sample Output 1

~141~ in base ~2~ is ~10001101~. The average digit is ~\dfrac{1+0+0+0+1+1+0+1}{8} = 0.5 = \dfrac{2-1}{2}~. Therefore, ~141~ is ~2~-balanced.

~141~ in base ~3~ is ~12020~. The average digit is ~\dfrac{1+2+0+2+0}{5} = 1 = \dfrac{3-1}{2}~. Therefore, ~141~ is ~3~-balanced.

~141~ in base ~4~ is ~2031~. The average digit is ~\dfrac{2+0+3+1}{4} = 1.5 = \dfrac{4-1}{2}~. Therefore, ~141~ is ~4~-balanced.

Lastly, ~141 \ge 100~.

Sample Input 2

7 10000000000

Sample Output 2

16926961207710

Hint

Feel free to use these code snippets as part of your solution.

// Important: If x is 0, the result is undefined.
int base_2_length(unsigned long long x) {
  return 64-__builtin_clzll(x);
}

int base_2_sum(unsigned long long x) {
  return __builtin_popcountll(x);
}