HU 6025 Copreme Sequence-プレフィックスと&拡張子と

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=6025
Copreme Sequence
Time Limit：2000/1000 MS（Java/Others）    Memory Limit：1313131313727 K（Java/Others）Total Submission（s）：666    Acceepted Submission(s)：336
Problem Description
Do ouk know what is caled`Copreme Sequence'？That is a sequence consists of 
n positive integers、and the GCD(Gretest Common Divisor)of them is equal to 1.
‘Copreme Sequence’is ease to find because of its restication.But we can try to maximize the GCD of the integers by removing exactly one integer.Now given a sequence，please maxize the GCD of elemens.emens.ems.
 
Input
The first line of the input contains an integer 
T（1≦T≦10）、denoting the number of test cases.
In each test case，there is an integer 
n（3≦n≦100000） in the first line，denoting the number of integers in the sequence.
The n the follwing line consists of 
n integers 
a 1，a 2，…，an（1≦ai≦109），denoting the elemens in the sequence.
 
Output
For each test case、print a single line a single integer、denoting the maximum GCD.
 
Sample Input

 
   

     3 3 1 1 1 5 2 2 2 3 2 4 1 2 4 8 
   
 
  

题解：

l[i]为前i个数的gcd， r[i]为后i个数的gcd。

假设被删除的数的下标为i， 则 删除该数后的gcd为： gcd(l[i-1], r[i+1])， 枚举i，取最大值。

学习之处：

当提到在序列里删除一段连续的数时，可以用前缀和+后缀和。

例如：http://blog.csdn.net/dolfamingo/article/details/71001021

代码如下：

#include
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int maxn = 1e5+10;

int n;
int a[maxn], l[maxn], r[maxn];

int gcd(int a, int b)
{
    return b==0?a:(gcd(b,a%b));
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1; i<=n; i++)
        scanf("%d",&a[i]);

    l[1] = a[1]; r[n] = a[n];
    for(int i = 2; i<=n; i++)
        l[i] = gcd(l[i-1], a[i]);
    for(int i = n-1; i>=1; i--)
        r[i] = gcd(r[i+1], a[i]);

    int ans = 1;
    l[0] = a[2]; r[n+1] = a[n-1];
    for(int i = 1; i<=n; i++)
        ans = max(ans, gcd(l[i-1], r[i+1]) );
    cout<