有趣的数学(1)

[gcd相减]

题意:

https://codeforces.ml/contest/1459/problem/C

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,a2+bj…,an+bj

就是对于每个b[j],求gcd(a1+bj,a2+bj,......an+bj);

思路:

gcd(a1+bj,a2+bj,......an+bj) = gcd(a1+bj,a2-a1,a3-a1,......,an-a1) => gcd(a1+bj,G);

G可以直接求出,然后答案就出来了.

gcd相减挺常见的.

上一篇:python数据可视化之matplotlib(下)


下一篇:Python数据可视化之matplotlib实践 源码 第一篇 入门 第二章