Loj #3096. 「SNOI2019」数论

题目描述

给出正整数 \(P, Q, T\)，大小为 \(n\) 的整数集 \(A\) 和大小为 \(m\) 的整数集 \(B\)，请你求出：

换言之，就是问有多少个小于 \(T\) 的非负整数 \(x\) 满足：\(x\) 除以 \(P\) 的余数属于 \(A\) 且 \(x\) 除以 \(Q\) 的余数属于 \(B\)。

输入格式

第一行 \(5\) 个用空格隔开的整数 \(P,Q,n,m,T\)。

第二行 \(n\) 个用空格隔开的整数，表示集合 \(A=\{A_1,A_2,\dots ,A_n\}\)。保证 \(A_i\) 两两不同，且 \(0 \le A_i < P\)。

第三行 \(m\) 个用空格隔开的整数，表示集合 \(B=\{B_1,B_2,\dots ,B_m\}\)。保证 \(B_i\) 两两不同，且 \(0 \le B_i < Q\)。

输出格式

输出一行一个整数表示答案。

数据范围与提示

对于所有数据，\(1 \le n, m \le 10^6, 1 \le P, Q \le 10^6, 1 \le T \le 10^{18}\)。

* 对于 \(10\%\) 的数据，\(T \le 10^6\)。

* 对于另外 \(20\%\) 的数据，\(P, Q \le 1000\)。

* 对于另外 \(10\%\) 的数据，\(T\) 是 \(P, Q\) 的公倍数。

* 对于另外 \(10\%\) 的数据，\(P, Q\) 互质，且 \(P,Q \le 10^5\)。

* 对于另外 \(10\%\) 的数据，\(P, Q\) 互质。

\(\\\)

考虑枚举\(a_i\)，然后计算有多少个\(x\)满足\(x\%P =a_i\)且\(x\%Q\in B\)。

首先\(x\)可以表示为\(a_i+P*t\)，然后\((a_i+P*t)\%Q\)是有循环的。具体来说是\(\gcd(P,Q)\)个长为\(\frac{Q}{\gcd(P,Q)}\)的环。知道这个过后就很好做了。

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 1000005

using namespace std;

inline ll Get() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

ll P,Q,T;

ll ans;

int n,m;

int a[N],b[N];

ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}

ll lcm;

int sum[N];

bool vis[N];

int pre[N],tot[N];

int cir;

bool key[N];

int rk[N];

int main() {

	P=Get(),Q=Get(),n=Get(),m=Get(),T=Get();

	cir=Q/gcd(P,Q);

	for(int i=1;i<=n;i++) a[i]=Get();

	for(int i=1;i<=m;i++) {

		b[i]=Get(),sum[b[i]]++;

		key[b[i]]=1;

	}

	for(int i=0;i<Q;i++) {

		if(vis[i]) continue ;

		vis[i]=1;

		int now,last=i;

		rk[i]=1;

		for(now=(last+P)%Q;now!=i;last=now,now=(now+P)%Q) {

			rk[now]=rk[last]+1;

			sum[now]+=sum[last];

			vis[now]=1;

		}

		tot[i]=sum[last];

		for(int j=(i+P)%Q;j!=i;j=(j+P)%Q) tot[j]=sum[last];

	}

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

		if(a[i]>=T) continue ;

		ll lim=(T-1-a[i])/P;

		ll A=a[i]%Q,B=(A+lim%cir*P)%Q;

		ans+=lim/cir*tot[A];

		if(rk[A]<=rk[B]) ans+=sum[B]-sum[A]+key[A];

		else ans+=tot[A]-(sum[A]-sum[B]-key[A]);

	}

	cout<<ans;

	return 0;

}