原題鏈接https://www.luogu.org/problem/show?pid=1890
暴力中的暴力。
對于每一組詢問l..r，我們先循環暴力枚舉l..r中最大值到1，再暴力循環l..r的每一個數，判斷前一重循環能否整除后一重，如果全部都能，則可判定它就是l..r的最大公因數。
時間復雜度\(O(mn*maxnum)\)。如果帶入如果帶入極值，需要執行\(10^{18}\)次。果斷超時。稍微優化的暴力。
對于每一組詢問，我們循環l..r的每一個數，然后再像這樣：ans=gcd(ans,a[i]);。ans初值為a[l]。
這樣的時間復雜度\(O(mn*logmaxnum)\)。代入極值：\(1000*1000000*30=3*10^{10}\)。還是會超時.
核心代碼：
ans=a[l];
for(int j=l;j<=r;++j)ans=gcd(ans,a[j]);3.動態規劃
設f[i][j]表示a[i..j]的最大公因數，則我們有狀態轉移方程：
\[f[i][j]=gcd(f[i][j-1],a[j])\]
這個方程是十分好推的。初值是這樣的：
\[f[i][i]=a[i]\]
計算dp的時間是\(O(n^2)\)，回答詢問要\(O(1)\)，共m次詢問，有\(O(n^2+m)\)的總時間復雜度。最多需要執行\(2*10^6\)次。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(register int i=(a);i<=(n);++i)
#define per(i,a,n) for(register int i=(a);i>=(n);--i)
#define fec(i,x) for(register int i=head[x];i;i=Next[i])
#define debug(x) printf("debug:%s=%d\n",#x,x)
#define mem(a,x) memset(a,x,sizeof(a))
template<typename A>inline void read(A&a){a=0;int f=1,c=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')f*=-1;}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}a*=f;}
template<typename A,typename B>inline void read(A&a,B&b){read(a);read(b);}
template<typename A,typename B,typename C>inline void read(A&a,B&b,C&c){read(a);read(b);read(c);}
template<typename A>A gcd(const A&m,const A&n){return m%n==0?n:gcd(n,m%n);}const int maxn=1000+7;
int n,m,a[maxn],f[maxn][maxn],l,r;void dp(){rep(i,1,n)rep(j,i+1,n)f[i][j]=gcd(f[i][j-1],a[j]);
}void Init(){read(n,m);rep(i,1,n)read(a[i]),f[i][i]=a[i];
}void Work(){dp();rep(i,1,m){read(l,r);printf("%d\n",f[l][r]);}
}int main(){Init();Work();return 0;
} 
)
