自动搬运

查看原文

来自洛谷，原作者为

	Vocalise 「不入流的划水选手」

搬运于2025-08-24 22:09:38，当前版本为作者最后更新于2021-02-16 21:50:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

求 $T$ 以内模 $P$ 值属于集合 $A$ 且 模 $B$ 值属于集合 $B$ 的数的数量。

$T\le 10^{18},P,Q,|A|,|B|\le 10^6$

首先对一个模型作介绍。

对于 $[0,Q)$ 中的数都建立一个点，若点 $i$ 连一条边至 $(i+P)\mod Q$，那么整个图会分为 $\gcd(P,Q)$ 个独立的环，每个环的点数是 $\dfrac{\operatorname{lcm(P,Q)}}{P}$。

说明：

每一个点走若干个 $P$ 步回到自己，同时经过了若干个 $Q$ 总长，因此经过的总长是 $\operatorname{lcm(P,Q)}$，点数 $\dfrac{\operatorname{lcm(P,Q)}}{P}$。而总点数 $Q$，所以环数 $Q/(\dfrac{\operatorname{lcm(P,Q)}}{P})=\gcd(P,Q)$。

假设 $P \le Q$。因为 $[0,P)$ 中的数要不变地唯一对应到 $[0,Q)$ 中的一个数。

在这个图上考虑问题，我们可以枚举 $a_i$，在图上直接找到它，考虑它沿边走 $k$ 步得到的数是 $(a_i + kP)\mod Q$，我们需要计算包括自己，在 $T-1$ 以内，一共经过多少 $b_i$。

要解决的问题直观了起来。我们可以在图上标记所有 $b_i$ 权值为 $1$ 其余为 $0$，预处理环上总和与 $1$ 圈以内的前缀和。

对于 $a_i$，包括自己一共要统计 $\lfloor\dfrac{T-1-a_i}{P}\rfloor+1$ 个点。首先直接计算整圈，然后对于留下的不满一圈的路径，分类讨论一下计算即可。

要注意的是：前缀和中选定的起点值是 $0$ 还是总和；$t-1-a_i<0$ 要直接舍弃。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

typedef long long ll;
const int N = 1000001;

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

int gcd(int x,int y) { return !y ? x : gcd(y,x % y); }

int P,Q,n,m,a[N],b[N]; ll t;
int vis[N],at[N]; ll dist[N],ring[N],sum[N],len;

ll Prefix(ll a,ll x) {
	if(!x) return 0;
	ll b = (a + (x - 1) * P) % Q;
	if(x + dist[a] > len) return sum[a] - (ring[a] - ring[b] - at[a]);
	else return ring[b] - ring[a] + at[a];
}

ll Calc(ll T) {
	ll ans = 0;
	for(int i = 1;i <= n;i++) {
		if(T < a[i]) continue;
		ll st = (T - a[i]) / P + 1;
		ans += st / len * sum[a[i]] + Prefix(a[i],st % len);
	}
	return ans;
}

int main() {
	P = read(), Q = read(), n = read(), m = read(), t = read();
	if(P > Q) {
		std::swap(P,Q), std::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++) at[b[i]] = true;
	for(int i = 0;i < Q;i++) if(!vis[i]) {
		int p = i, k = (i + P) % Q;
		while(!vis[p]) {
			vis[p] = true, dist[k] = dist[p] + 1;
			ring[k] = ring[p] + at[k];
			p = k, k = (k + P) % Q;
		}
		k = (i + P) % Q, sum[i] = ring[i], ring[i] = dist[i] = 0;
		while(k != i) sum[k] = sum[i], k = (k + P) % Q;
	}
	len = Q / gcd(P,Q);
	std::printf("%lld\n",Calc(t - 1));
	return 0;
}