2022.11.17模拟赛题解

从今天起更换码风。

猜数字

两种做法：二分，哈希

二分

记函数 \(g(x)\) 表示数字 \(x\) 在 \(10\) 进制下的位数。
可以观察到对于正整数 \(k(k\ge 2)\)，都有 \(g(k^k)<g((k+1)^{k+1})\)，所以可以考虑二分答案，\(\rm check\) 的时候使用位数判断即可。
那么 \(k^k\) 的位数是多少呢？首先考虑 \(k\) 的位数。易得，\(k\) 的位数是 \(\lfloor \log _{10} d \rfloor +1\)。则 \(k^k\) 的位数是 \(\lfloor \log _{10} k^k \rfloor +1=\lfloor k\times \log _{10} k \rfloor +1\)。
理解上面这个等式也很简单，若 \(10^x=k\)，则 \(10^{x\times k}=k^k\)。

const int N = 300005;
char s[N];
int n;
int calc(int x) // 计算x^x的位数
{ 
    return floor(x * log10(x)) + 1;
}
bool chk(int x) 
{
    return calc(x) >= n;
}
signed main() 
{
    scanf("%s", s + 1); n = strlen(s + 1);
    if (n == 1) 
    {
        if (s[1] == '1') write(1);
        else write(2);
        return 0;
    }
    int L = 1, R = 50000;
    while (L < R) 
    {
        int mid = L + R >> 1;
        if (chk(mid)) R = mid;
        else L = mid + 1;
    }
    write(R);
    return 0;
}

哈希

首先可以发现高精度取模是 $ \Omicron(len)$ 的。
对于 \(1\sim 50000\) 中所有的数都进行一次快速幂取模，如果和输入的数余数相同则大概率相同。多整几个模数即可。
代码略。