P5330 [SNOI2019] 数论
题目描述
给出正整数 $P,Q,T$ ,大小为 $n$ 的整数集 $A$ 和大小为 $m$ 的整数集 $B$ ,请你求出:
$$
\sum_{i=0}^{T-1}[(i\bmod P) \in A \land (i\bmod Q) \in B]
$$
换言之,就是问有多少个小于 $T$ 的非负整数 $x$ 满足:$x$ 除以 $P$ 的余数属于 $A$ 且 $x$ 除以 $Q$ 的余数属于 $B$。
输入格式
无
输出格式
无
说明/提示
对于所有数据,$1 \leq n,m \leq 10^6 , 1 \leq P,Q \leq 10^6 , 1 \leq T \leq 10^{18}$。
对于10%的数据,$T \leq 10^6$。
对于另外20%的数据,$P,Q \leq 1000$。
对于另外10%的数据,$T$是$P,Q$的公倍数。
对于另外10%的数据,$P,Q$互质,且$P,Q \leq 10^5$。
对于另外10%的数据,$P,Q$互质。
对于另外10%的数据,$P,Q \leq 10^5$。
对于余下30%的数据,无特殊限制。
- 2023.11.17 添加三组 hack 数据。