#P12968. [CCO 2025] Balanced Integer

[CCO 2025] Balanced Integer

题目背景

Abusing judging resources leads to an account ban.

You can self-test the first three test cases of each Subtask at the link: https://www.luogu.com.cn/problem/U576602 to avoid long judging wait times.

题目描述

Since the CCO often uses integers, Alice needs to learn about the integers! A positive integer nn can be written in base bb as the sequence dm1dm2d1d0d_{m-1}d_{m-2} \ldots d_{1}d_{0} if the following hold:

  • Each digit did_{i} is between 0 and b1b-1, inclusive.
  • dm1>0d_{m-1}>0.
  • $n=d_{m-1} \times b^{m-1}+d_{m-2} \times b^{m-2}+\cdots+d_{1} \times b^{1}+d_{0} \times b^{0}$.

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

An integer nn is bb-balanced if, when nn is written in base bb, the average of the digits is b12\frac{b-1}{2}. For example, 2025 is 19-balanced because 5+11+113=9=1912\frac{5+11+11}{3}=9=\frac{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 BB and NN, please help Alice find the minimum integer xx such that:

  • xx is bb-balanced, for all 2bB2 \leq b \leq B.
  • xNx \geq N.

输入格式

The first line of input contains two space-separated integers BB and NN (N1N \geq 1).

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

输出格式

Output the minimum integer xx from the problem statement.

4 100
141
7 10000000000
16926961207710

提示

Sample 1 Explanation

141141 in base 22 is 1000110110001101. The average digit is

1+0+0+0+1+1+0+18=0.5=212.\frac{1+0+0+0+1+1+0+1}{8}=0.5=\frac{2-1}{2}.

Therefore, 141141 is 2-balanced.

141141 in base 3 is 1202012020. The average digit is

1+2+0+2+05=1=312.\frac{1+2+0+2+0}{5}=1=\frac{3-1}{2}.

Therefore, 141141 is 3-balanced.

141141 in base 4 is 20312031. The average digit is

2+0+3+14=1.5=412.\frac{2+0+3+1}{4}=1.5=\frac{4-1}{2}.

Therefore, 141141 is 4-balanced.

Lastly, 141100141 \geq 100.

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);
}

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

Marks Awarded Bounds on BB Bounds on NN
2 marks 2B72 \leq B \leq 7 1N1041 \leq N \leq 10^{4}
6 marks 2B62 \leq B \leq 6 N=1010N = 10^{10}
2 marks 2B72 \leq B \leq 7 None
9 marks 8B118 \leq B \leq 11 N=1N = 1
4 marks B=8B = 8 None
2 marks 9B119 \leq B \leq 11