题意分析

题目要求找出在给定区间$(r_1, r_2)$内最大的整数$i$，使得$i$在基数$B_1$下的数字表示与$i \times c$在基数$B_2$下的数字表示完全相同，其中$c$是某个正整数。本质上是要寻找满足特定进制转换关系的数字。

解题思路

1. 进制转换：对于每个候选数字$i$，将其从$B_1$进制转换为$B_2$进制表示的数字值。
2. 倍数验证：检查转换后的数值是否能被$i$整除，即是否存在整数$c$满足条件。
3. 区间搜索：在给定区间内从大到小搜索满足条件的最大$i$。

实现步骤

1. 输入处理：读取测试用例数量$n$和各个测试参数。
2. 候选数字遍历：对每个测试用例，在$(r_1, r_2)$区间内遍历数字。
3. 进制转换验证：
   • 将当前数字$i$视为$B_1$进制数
   • 计算其在$B_2$进制下的数值
   • 验证该数值是否是$i$的整数倍
4. 结果输出：输出满足条件的最大数字或提示不存在。

C++实现

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;

bool judge(int r, int b1, int b2) {
    LL ret = 0, t = 1;
    int x = r;
    while(x) {
        ret += x % b1 * t;  // 将B1进制数转换为B2进制数值
        x /= b1;
        t *= b2;
    }
    return ret % r == 0;    // 检查是否是r的整数倍
}

int main() {
    int n, b1, b2, r1, r2;
    scanf("%d", &n);
    while(n--) {
        scanf("%d%d%d%d", &b1, &b2, &r1, &r2);

        int ans = r1;
        // 从大到小搜索满足条件的最大i
        for(int i = r2 - 1; i > r1; i--) {
            if(judge(i, b1, b2)) {
                ans = i;
                break;
            }
        }

        if(ans == r1)
            printf("Non-existent.\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}

代码说明

1. judge函数：

   • 参数：当前数字$r$，基数$b1$和$b2$
   • 功能：将$r$视为$b1$进制数，计算其在$b2$进制下的数值
   • 返回值：该数值是否是$r$的整数倍

2. 主函数逻辑：

   • 读取输入参数
   • 从区间上限开始向下搜索
   • 使用judge函数验证每个候选数字
   • 输出最大满足条件的数字或不存在提示

3. 优化处理：

   • 从大到小搜索，找到第一个满足条件的数字即可返回
   • 使用long long类型防止数值溢出
   • 时间复杂度为$O(n \times (r_2-r_1))$，在题目限制范围内高效