Loj #3096. 「SNOI2019」数论

题目描述

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

[sum_{i=0}^{T-1} [(iin Apmod P)land(iin Bpmod Q)] ]

换言之，就是问有多少个小于 (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\%Qin 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;
}