题解：P14168 [Algo Beat Contest 002.5 C] 数数题 (count)

A7F3jK9pR0xf_ · 2025-10-06 15:09:11 · 题解

水题。

注意到 x^a\bmod b\in [0,b)，所以我们可以去枚举 x^a\bmod b 的值。然后去一步步反着推回去。

首先观察到 f(x)\bmod 10\neq 0，所以枚举的时候要把 10|i 的 i 给删掉。

然后把第一层 f 拆了，可以得到 f(x)=f(i)\times 10^j-c，为什么要乘 10^j，是因为计算 f 的时候会把前导 0 删掉，而实际的值可能后面有很多 0。

然后判断 10|f(x)，如果是就 pass 掉。

接着把第二层 f 拆了，可以得到 x=f(f(x))\times 10^k，后面乘 10^k 同理。

最后去验证 x\in [l,r] 且 x^a\bmod b=i 即可。注意要特判拆完 f 后可能会出现负数或者超过 10^{18}。

时间复杂度 O(Tb\log a) 再乘上枚举 j,k 的 100 的常数，基本不需要卡什么常。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const ll inf = 1e18;
int a, b, c;
il ll ppow(ll x, ll y)
{
    ll ans = 1;
    for(;y > 0;x = x * x % b, y >>= 1)
        if(y & 1) ans = ans * x % b;
    return ans;
}
il ll calc(ll x)
{
    ll ans = 0;
    while(x)
    {
        ans = ans * 10 + x % 10;
        x /= 10;
    }
    return ans;
}
ll p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000ll};
unordered_set<ll> ss;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        ll l, r;
        cin >> l >> r >> a >> b >> c;
        ss.clear();
        for(int i = 0;i < b;++i)
        {
            if(i % 10 == 0) continue;
            ll fxx = calc(i);
            for(int j = 0;j <= 10;++j)
            {
                if(fxx >= (inf + c) / p10[j]) break;
                ll fx = fxx * p10[j] - c;
                if(fx < 0 || fx % 10 == 0) continue;
                ll x = calc(fx);
                if(x < 0 || x > r) continue;
                for(int k = 0;k <= 10;++k)
                {
                    if(x >= inf / p10[k]) break;
                    ll xx = x * p10[k];
                    if(l <= xx && xx <= r && ppow(xx % b, a) == i) ss.insert(xx);
                }
            }
        }
        cout << ss.size() << "\n";
    }
    return 0;
}