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}{}

如果你真的按照这篇文章这么做的话，你多半会：

如果没T当我没说，拜谢

优化

暴力的思路是暴力因式分解，但是这样做有十分甚至九分的可能会超时。那怎么优化呢？

可以维护一个数组 \tt mz，\tt mz[\rm{i}\tt] 代表 i 的最小质因数，这样就可以避免每次标记都要遍历半天的问题。

怎么维护呢？

显然当 i 是质数时，\tt mz[\rm{i}\tt] = \rm i。当 i 不是质数的时候，那么 i 必然可以拆分成 p\times j；根据线性筛的原理，当筛到 p 的时候，p\times j 将会被 p 标记。因此，只需要在线性筛中加入一行：

mz[i * pm_list[j]] = pm_list[j];

就可以达到相应效果。

总的线性筛代码如下：

void make_prime_list(int n)
{
    int i, j;
    is_prime[1] = 0;
    for (i = 2; i <= n; i++) {
        if (is_prime[i] == 0) pm_list[++pm_count] = i, mz[pm_list[pm_count]] = i;
        for (j = 1; j <= pm_count && i * pm_list[j] <= n; j++) {
            is_prime[i * pm_list[j]] = 1;
            mz[i * pm_list[j]] = pm_list[j];
            if (i % pm_list[j] == 0) break;
        }
    }
}

主函数核心部分代码：

while (a > 1) {
    vs[mz[a]] = 1;
    a /= mz[a];
}