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;
}