[NOIP 2014 시 뮬 레이 션 8.17] Magical GCD / / 2018.2.5

제목.
Description 정수 로 구 성 된 시퀀스 에 대해 Magical GCD 는 한 구간 의 길이 에 해당 구간 내 모든 숫자 를 곱 하 는 최대 공약수 입 니 다.이 서열 에서 가장 큰 Magical GCD 를 구 할 서열 을 드 리 겠 습 니 다.Input
단일 테스트 점 에는 여러 그룹의 데이터 가 포함 되 어 있다.입력 한 첫 줄 은 정수 T 로 데이터 그룹 수 를 표시 합 니 다.각 그룹의 데이터 의 첫 줄 은 하나의 정수 N 으로 서열 의 길 이 를 설명 한다.다음 N 개의 숫자, 이 시퀀스 요소 A [i] 를 설명 합 니 다.
Output
각 그룹의 테스트 데이터 출력 줄 에 하나의 정 수 를 포함 하여 서열 이 가장 큰 Magical GCD 를 표시 합 니 다.
Data Constraint
30% 포인트 의 데이터 에 대해 N < = 10, T < = 11, 000, A [i] < = 100 은 남 은 70% 포인트 의 데이터 에 대해 N < = 100, 000, T < = 20, A [i] < = 10 ^ 12 C / C + + 선수 의 읽 기와 출력 64 비트 정 수 는% lld 를 사용 하 십시오.
문제 풀이 의 사고 방향.
이 문 제 는 RMQ 처럼 보이 지만 데이터 가 크 지 않 습 니 다.직접 폭력 으로 매 거 한다 ['기억 화 매 거']. 당연히 최적화 해 야 한다 (그렇지 않 으 면 O (n 의 제곱).왼쪽 에서 오른쪽으로 열거 하고 ans 로 최대 치 를 기록 합 니 다. 매번 업데이트 할 때마다...
코드

#include
#include
#include
using namespace std; 
long long t,n,ans,a[100001],b[100001];
int d[100001],c[100001];
long long gf(long long x,long long y)
{return x%y?gf(y,x%y):y;}//     
int main()
{
    scanf("%lld",&t);
    while (t--)
    {
        ans=0;
        scanf("%lld",&n);
        for (int i=1;i<=n;i++)
        {scanf("%lld",&a[i]); b[i]=a[i]; c[i]=i-1; d[i]=i+1;} //c         ，d         
        for (int i=1;i<=n;i++)
         for (int j=1;j<=i;j=d[j])
         {
            b[j]=gf(b[j],a[i]);//      
            ans=max(b[j]*(i-j+1),ans);//   Magical GCD 
            if(b[j]==b[j-1])//       Magical GCD   ，    、     ，      “     ”
            {
                d[c[j]]=d[j];
                c[d[j]]=c[j];
            }
         }
         printf("%lld
",ans);
    }
}