题解：P5330 [SNOI2019] 数论

依旧喵喵题。

首先考虑怎么刻画取模之后的限制，我们考虑进行图论建模，对

[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)

。

CPP

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

题解：P5330 [SNOI2019] 数论

文章操作

相关推荐

评论

题解：P5330 [SNOI2019] 数论