题目传送门
题目大意：
给定一个长度为 \(n\) 的单增序列 \(a\) 和一个长度为 \(m\) 的序列 \(b\)，询问是否存在一个正整数 \(y\) 使得 \(a_1\equiv a_2\equiv\cdots \equiv a_n\equiv y\space (\bmod\space p)\)，且 \(p\) 在序列 \(b\) 中出现过。
思路：
将条件转化一下，得：是否存在一个正整数 \(y\) 使得 \(p \mid (a_2 - a_1),p \mid (a_3 - a_2)\cdots p \mid (a_n - a_{n - 1})\)，说白了就是我们要寻找的 \(p\) 是序列 \(a\) 所有相邻项之差的因数。
所以先构造一个差分序列 \(c\)，然后求出 \(c\) 中所有数的最大公因数 \(d\)。
引理：
任意 \(n\) 个正整数 \((n\ge 2)\) 的所有公因数都是这 \(n\) 个数的最大公因数的因数。
证明：
先考虑两个数的情况。
设这两个数是 \(a,b\)，考虑将它们分解质因数，并将质因数对齐，得：
\[a = p_{1}^{a_1}p_{2}^{a_2}\cdots p_{k}^{a_k} \]\[b = p_{1}^{b_1}p_{2}^{b_2}\cdots p_{k}^{b_k} \]对于 \(a,b\) 的任意因数 \(d\)，我们也将它分解质因数并对齐，得：
\[d = p_{1}^{c_1}p_{2}^{c_2}\cdots p_{k}^{c_k} \]注意！这里的 \(a_i\) 和 \(b_i\) 可能为 \(0\)！（因为只是对齐处理，可能并不含此质因子）
根据因数的定义可得：
\[c_i \le \min(a_i, b_i),i\in [1, k] \]而对于 \(\gcd(a, b)\)，此时有：
\[c_i = \min(a_i, b_i),i\in [1, k] \]也就是取等了！
所以不难得出，\(a,b\) 所有公因数都是最大公因数的因数。
那么推广到 \(n\) 个数的情况就不难了，请读者自行证明。
其实挺显然的吧。
有了这个引理，我们就只需要找序列 \(b\) 中是否存在一个数是 \(d\) 的因数即可。
然后就是一些小细节了。
时间复杂度为 \(O(n + m + \log(\max\{c_i\}))\)。
\(\texttt{Code:}\)
#include <iostream>
using namespace std;
const int N = 300010;
typedef long long ll;
int n, m;
ll a[N], p[N], c[N];
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a % b);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= m; i++) scanf("%lld", &p[i]);
for(int i = 1; i <= n; i++) c[i] = a[i] - a[i - 1];
ll d = c[2];
for(int i = 3; i <= n; i++)
d = gcd(d, c[i]);
bool flag = false;
ll fac, ans;
for(int i = 1; i <= m; i++)
if(d % p[i] == 0) {
puts("YES");
flag = true;
fac = p[i];
ans = i;
break;
}
if(!flag) {
puts("NO");
return 0;
}
if(c[1] % fac == 0) printf("%lld %lld", fac, ans);
else printf("%lld %lld", c[1] % fac, ans);
return 0;
}