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{-500px}{} 如果你真的按照这 […]