题解：P5330 [SNOI2019] 数论

ini2015_____ · 2025-11-23 16:08:27 · 题解

依旧喵喵题。

首先考虑怎么刻画取模之后的限制，我们考虑进行图论建模，对 [0,Q) 内每一个数建一个点，然后每个点 i 连一个指向 (i+P)\bmod Q 的出边，于是这个图会被分成 \gcd(P,Q) 个环，每个环长是 \frac{Q}{\gcd(P,Q)}。

然后我们在环上刻画我们需要的条件。我们枚举一个起始点 a_i，然后每次在环上跳，跳 t 次相当于跳到 (a_i+tP)\bmod Q，最多能跳 \lfloor \frac{T-1-a_i}P\rfloor 次，每个跳到的 b_i 就是合法的。

于是就很简单了，我们处理出来环上 b_i 的个数，然后对于一个 a_i 我们只需要知道统计整环的个数和环上的一段，用前缀和统计即可。

时间复杂度 O(P+Q)。

const int N=1e6+5,inf=1e9+7;
ll p,q,n,m,t,len;
ll a[N],b[N];
ll seq[N],pre[N],sum[N];
bool tag[N],vis[N];
ll query(ll x,ll L){
    if(!L)return 0;
    ll y=(x+(L-1)*p)%q;
    if(L+seq[x]>len)return sum[x]-(pre[x]-pre[y]-tag[x]);
    return pre[y]-pre[x]+tag[x];
}
int main(){
    p=read(),q=read(),n=read(),m=read(),t=read();
    if(p>q){
        swap(p,q),swap(n,m);
        for(int i=1;i<=m;i++)b[i]=read();
        for(int i=1;i<=n;i++)a[i]=read();
    }
    else{
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=m;i++)b[i]=read();
    }
    for(int i=1;i<=m;i++)tag[b[i]]=1;
    for(int i=0;i<q;i++)if(!vis[i]){
        int u=i,v=(u+p)%q;
        while(!vis[u]){
            vis[u]=1,seq[v]=seq[u]+1;
            pre[v]=pre[u]+tag[v];
            u=v,v=(u+p)%q;
        }
        v=(i+p)%q,sum[i]=pre[i],pre[i]=seq[i]=0;
        while(v!=i)sum[v]=sum[i],v=(v+p)%q;
    }
    len=q/__gcd(p,q);
    ll ans=0;
    for(int i=1;i<=n;i++)if(t-1>=a[i]){
        ll st=(t-1-a[i])/p+1;
        ans+=(st/len)*sum[a[i]]+query(a[i],st%len); 
    }
    printf("%lld\n",ans);
    return 0;
}
//  think twice,code once