691C. Row GCD You are given two positive integer sequences a1,…,an and b1,…,bm. For each j=1,…,m find the greatest common divisor of a1+bj,…,an+bj.
引理: gcd(x,y)=gcd(x,y−x)
引理: 可以拓展到 **数组 gcd数值上等于数组差分 gcd **;证明显然,略
注意该命题在数组及其差分上取子数组时上并不成立,如 991F. Typora怎么快速加页面内链接… 记gpfx=gcd(a2−a1,a3−a2,…an−an−1)
于本题利用gcd(a1+b1,a2+b1,…an+b1)=gcd(a1+b1,a2−a1,a3−a2,…an−an−1)=gcd(a1+b1,gpfx)即可
int main() { fast_io(); /* El Psy Kongroo */ ll n,m; cin >> n >> m; vector<ll> a(n); for (ll& x: a) cin >> x; // gcd(a_1+b_1,a_2+b_1,....