C

DHeasy · 2025-07-28 13:23:56 · 题解

首先 f(x)\bmod 10 \not= 0。

注意到 b 很小，考虑枚举 x^a\bmod b，即 f(f(x)+c)。

而对于任意的 x,y\in \N^* 满足 f(x)=f(y)，都有 x=y\times 10^k,k\in \N。考虑暴力枚举 f(x)+c，检查 f(x) 是否存在，再用同样方法枚举 x 并检查即可。

时间复杂度 O(T\times\log^2V\times b\log a)，其中 V 为 l,r 的值域。

#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline ll read(){
    ll res=0ll,f=1;
    char c;
    for(;(c=getchar())<'0'||c>'9';c=='-'?f=-f:0);
    while(c>='0' && c<='9') res=(res<<1) + (res<<3) + c-'0',c=getchar();
    return res*f;
}
inline ll Max(re ll x,re ll y){return x>y?x:y;}
inline ll Min(re ll x,re ll y){return x<y?x:y;}
inline void cmax(re auto &x,re auto y){x=Max(x,y);}
inline void cmin(re auto &x,re auto y){x=Min(x,y);}
/*-----------------*/
ll l,r,a,c;
ull b;
ll num[20],k,ans;
inline ull qpow(re ull x,re ull y){
    ull sum=1,now=x%b;
    while(y){
        if(y&1) sum=sum*now%b;
        y>>=1,now=now*now%b;
    }
    return sum;
}
inline ll f(re ll x){
    if(x<0) return 0;
    ll p=0;k=0;
    while(x) num[++k]=(x%10),x/=10;
    for(re int i=1;i<=k;i++) p=p*10+num[i];
    return p;
}
int main(){
    int T;T=read();
    while(T--){
        l=read();r=read();ans=0;
        a=read();b=read();c=read();
        for(re ll i=0;i<b;i++){
            if((ull)i%10==0) continue;
            for(re ll x=f(i);f(x-c)<=r;x*=10){
                if(x-c<0) continue;
                if((ull)(x-c)%10==0) continue;
                for(re ll y=f(x-c);y<=r;y=y*10){
                    if(y<l) continue;
                    if(qpow(y,a)==i) ans++;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}