Luogu P5330 [SNOI2019]数论

题目

如果\(P>Q\)的话我们先交换一下\(P,Q\)。

我们先枚举所有满足第一个条件的数，对于\(x\equiv a_i(mod\ P)\)，设\(x=a_i+kP(k\in[0,\lfloor\frac{T-a_i}P\rfloor])\)。

然后能够产生贡献的数就是\(x\%Q\in B\)的数。

而且我们知道，当\(Q|kP\)时\(x\%Q\)就会产生循环，也就是说对\(k\)而言，\(M=\frac Q{(P,Q)}\)是循环节。

所以我们可以将计算\(k\in[0,\lfloor\frac{T-a_i}P\rfloor]\)的贡献拆成\(k\in[0,M]\)和\(k\in[0,t](t\in[0,M])\)两部分。

这个贡献我们可以采用这样的方法来算：

建\(0\sim Q-1\)个点的图，\(B_i\)的权值为\(1\)，其它的权值为\(0\)。并对\(x->(x+P)\%Q\)建边。

这样我们要求的就变成了从\(a_i\)出发经过\(t\)条边的经过的点权和。

易知这个图是由\((P,Q)\)个环构成的，每个环上有\(\frac Q{(P,Q)}\)个点。

所以我们处理出每个环的点权和以及环上点的点权前缀和，然后就可以计算答案了。

#include<bits/stdc++.h>

#define pb push_back

#define ll long long

using namespace std;

namespace IO

{

    char ibuf[(1<<21)+1],*iS,*iT;

    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}

    int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}

    ll readl(){ll x=0;int c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}

}

using namespace IO;

const int N=1000007;

int A[N],B[N],t[N],val[N],col[N],pos[N],P,Q;ll lim[N];vector<int>dot[N],sum[N];

int dfs(int u,int num)

{

    if(col[u]) return 0;

    col[u]=num,dot[col[u]].pb(u);

    return t[u]+dfs((u+P)%Q,num);

}

int cal(int x,int l){return sum[col[x]][pos[x]+l]-sum[col[x]][pos[x]];}

int main()

{

    int i,j,tmp,num=0,n,m,M;ll ans=0,T;

    P=read(),Q=read(),n=read(),m=read(),T=readl()-1;

    for(i=1;i<=n;++i) A[i]=read();

    for(i=1;i<=m;++i) B[i]=read();

    if(P>Q) swap(P,Q),swap(n,m),swap(A,B);

    M=Q/__gcd(P,Q);

    for(i=1;i<=m;++i) t[B[i]]=1;

    for(i=1;i<=n;++i) lim[i]=(T-A[i])/P;

    for(i=0;i<Q;++i) if(!col[i]) ++num,val[num]=dfs(i,num);

    for(i=1;i<=num;++i)

    {

        for(j=0;j<dot[i].size();++j) pos[dot[i][j]]=j;

        tmp=dot[i].size()-1;

        for(j=0;j<tmp;++j) dot[i].pb(dot[i][j]);

        sum[i].pb(t[dot[i][0]]);

        for(j=1;j<dot[i].size();++j) sum[i].pb(sum[i][j-1]+t[dot[i][j]]);

    }

    for(i=1;i<=n;++i) ans+=lim[i]/M*val[col[A[i]]]+cal(A[i],lim[i]%M)+t[A[i]];

    return !printf("%lld",ans);

}

巴特西

Luogu P5330 [SNOI2019]数论

最新文章

热门文章