6025专题

HDU - 6025 Coprime Sequence 典型前缀后缀

题意:给你一个序列,任意去掉一个,问整个序列的最大公约数。 前缀和,后缀和思想 求前缀最大公约数,后缀最大公约数,然后找gcd(前缀gcd,后缀gcd)中最大的。 具体思想:开两个数组,第一个数组a保存前缀gcd,a[i]表示,从1到i的最大公约数。第二个数组b保存后缀gcd,b[i]表示,从n到i的最大公约数。 去掉第i个数的最大公约数为gcd(a[i-1],b[i+1]).over!