#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 can be written in base as the sequence if the following hold:
- Each digit is between 0 and , inclusive.
- .
- $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 because $2025=5 \times 19^{2}+11 \times 19^{1}+11 \times 19^{0}$.
An integer is -balanced if, when is written in base , the average of the digits is . For example, 2025 is 19-balanced because .
Alice can easily find integers that are 19-balanced. However, she has trouble finding integers that are balanced in multiple ways. Given and , please help Alice find the minimum integer such that:
- is -balanced, for all .
- .
输入格式
The first line of input contains two space-separated integers and ().
It is guaranteed that the answer does not exceed .
输出格式
Output the minimum integer from the problem statement.
4 100
141
7 10000000000
16926961207710
提示
Sample 1 Explanation
in base is . The average digit is
Therefore, is 2-balanced.
in base 3 is . The average digit is
Therefore, is 3-balanced.
in base 4 is . The average digit is
Therefore, is 4-balanced.
Lastly, .
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 marks are distributed:
Marks Awarded | Bounds on | Bounds on |
---|---|---|
2 marks | ||
6 marks | ||
2 marks | None | |
9 marks | ||
4 marks | None | |
2 marks |