自动搬运

查看原文

来自洛谷，原作者为

	TensorFlow_js null

搬运于2025-08-24 22:25:12，当前版本为作者最后更新于2022-10-12 00:55:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

0. 题意简述

给定 $y,l$，求最大的 $b$ 使 $(y)_b$ 仅含有数字 $0-9$，且将 $(y)_b$ 看作十进制数字时 $(y)_b >= l$。$(10\le l\le y\le 10^{18})$

1. 做法详解

这里是一种基于二分和预处理的做法。

首先很容易想到，对于下限 $l$，可以二分答案。

具体就是把 $l$ 当作 $b$ 进制数，然后把 $l$ 转回 $10$ 进制，看一下是否大于 $y$，若大于则代表此时的 $b$ 不符合条件，然后枚举 $b$ 的上限。对于“只包含十进制数字”这条要求，我们暴力从上限往下枚举即可。时间复杂度 $\mathcal{O}(\log y+b_{max}-b_{ans})$。

如果满足“只包含十进制数字”的答案很稀疏的话，这个时间复杂度显然是过不去的，而事实就是这样。

我们仔细想想，会发现：如果过不去，说明 $b$ 的上限与实际值的差很大。这说明实际值一定大不到哪去。

考虑预处理出从 $10$ 开始的一定范围内中的最大答案，然后再加入卡时，如果枚举到某个时间点时还没有出答案，就直接输出预处理得到的结果。

这显然会牺牲一部分的正确性，但已经足以让我们通过 $48$ 个测试点。

再考虑观察答案可能的分布位置。

我们试着打个暴力，可以发现，当 $n$ 足够大时，答案集中分布在 $\frac{\sqrt n}{2}$ 附近。

于是我们又多通过了两个测试点。

再考虑答案的集中趋势是不行了，于是我们试试看极限情况 $y=10^{18}$ 时的数据。

我们会发现，在 $y$ 足够大，$l$ 略小的时候，答案即为 $\lfloor\frac{y}{k}\rfloor$，其中 $k$ 是一个较小的常数。

加上上述三个预处理即可通过本题。

2. 代码

#include<bits/stdc++.h>
template<typename T1, typename T2>
constexpr auto max (T1 a, T2 b) -> decltype(a + b) {
    if (a > b)return a;
    return b;
}
using namespace std;
using ll = long long;
constexpr ll maxn1 = 999999, maxn2 = 1000, maxms = 114.514;
//分别为：从 10 开始枚举时的上限；sqrt(y) 附近的波动范围；暴力枚举的时间上限
ll change (ll l, ll b, ll y) {//把 l 当作 b 进制数，然后把 l 转回 10 进制
    if (l < 10)return l;
    auto a = change (l / 10, b, y);
    if (a >= y / b + 1 || !~a)return -1;//细节：如果直接返回 10 进制的值会溢出，所以判断是否大于 y，若是则直接返回 -1
    return a * b + l % 10;
}
bool check (ll l, ll b) {//判断是否满足“只包含十进制数字”
    if (l < b)return l < 10;
    return check (l / b, b) && l % b < 10;
}
inline auto gettime ( ) {//获取时间（精确到毫秒）
    return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now ( ).time_since_epoch ( )).count ( );
}
int main ( ) {
    ll y, l, ans = -1, L = 10, R = 1e18, m, beg = gettime ( );
    //分别为：题目中的 y 与 l；预处理的答案；二分答案的上下界；二分答案的中值；程序开始运行的时间
    cin >> y >> l;R = y;
    while (L < R) {//二分答案上界
        m = L + R + 1 >> 1;
        if (change (l, m, y) != -1 && change (l, m, y) <= y)L = m;
        else R = m - 1;
    }
    for (ll i = 10;i <= maxn1 && i <= L;i++)//预处理1
        if (check (y, i))ans = max (ans, i);
    if (sqrt (y) > maxn2)//细节：若 sqrt(y) 小于 maxn2，则二分答案已经可以出结果，预处理反而会 RE
        for (ll i = max (sqrt (y) / 2 - maxn2 / 3, 0);i <= sqrt (y) / 2 + maxn2 / 3 && i <= L;i++)//预处理2
            if (check (y, i))ans = max (ans, i);
    if (y > maxn1)
        for (ll i = maxn1;y / i < L && i>1 && y / i > 10;i--)
            if (check (y, y / i))ans = max (ans, y / i);//预处理3
    while (gettime ( ) - beg < maxms) {//带卡时的暴力枚举
        if (check (y, L)) {
            cout << L << endl;
            return 0;
        }
        L--;
    }
    cout << ans << endl;
    return false;
}

3.总结

二分答案是一个很好用的方法，并且如果能看出一些答案的分布规律的话可以结合使用。

4.UPD

[2022-10-13 22:44] 优化了代码的可读性。