【LOJ#3096】[SNOI2019]数论

题面

LOJ

题解

考虑枚举一个\(A\)，然后考虑有多少个合法的\(B\)。

首先这个数可以写成\(a_i+kP\)的形式，那么它模\(Q\)的值成环。

所以我们预处理每个环内有多少个合法的\(b\)，再把\(b\)按照访问顺序记录一下，那么对于每一个\(a\)就可以直接算答案了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 1001000

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int A[MAX],B[MAX],ID[MAX];

vector<int> G[MAX];

int P,Q,D,n,m;ll T,ans;

int main()

{

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

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

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

	D=__gcd(P,Q);

	for(int i=0;i<D;++i)

	{

		int u=i,cnt=0;

		while(!cnt||u!=i)

		{

			ID[u]=++cnt;

			if(B[u])G[i].push_back(cnt);

			u=(u+P)%Q;

		}

	}

	ll c=1ll*P*Q/D;

	for(int i=1;i<=n;++i)

	{

		ll cir=(T-A[i])/c;

		ans+=cir*(int)(G[A[i]%D].size());

		ll st=(T-cir*c-A[i])/P;

		int L=ID[A[i]],R=ID[(A[i]+st*P)%Q];

		if(L<=R)

		{

			ans+=upper_bound(G[A[i]%D].begin(),G[A[i]%D].end(),R)-G[A[i]%D].begin();

			ans-=upper_bound(G[A[i]%D].begin(),G[A[i]%D].end(),L-1)-G[A[i]%D].begin();

		}

		else

		{

			swap(L,R);ans+=G[A[i]%D].size();

			L+=1;R-=1;if(L>R)continue;

			ans-=upper_bound(G[A[i]%D].begin(),G[A[i]%D].end(),R)-G[A[i]%D].begin();

			ans+=upper_bound(G[A[i]%D].begin(),G[A[i]%D].end(),L-1)-G[A[i]%D].begin();

		}

	}

	printf("%lld\n",ans);

	return 0;

}