SPOJ – 30919: GCDS – Sabbir and gcd problem 题解
SPOJ 原题传送门 洛谷RMJ传送门 这是一道数论题。 思路 因为要求找到的整数 $x$ 是一个互质于 $a_i$ 的数，所以很显然 $x$ 为质数的时候最优。 根据互质的一些性质，$a_i$ 和 $x$ 没有共同的质因数，所以可以标记所有 $a_i (1\le i\le n)$ 的质因数，然后选取最小的未被标记的质数。 举个例子： $\rm{a = \tt{[11, 45, 14, 19, 81]}}$ 标记如下 故选择13作为 $x$。 看到这里，就滚去写代码罢！ $$ \raisebox […]