题目描述
给定一行n个正整数a[1]..a[n]。
m次询问,每次询问给定一个区间[L,R],输出a[L]..a[R]的最大公因数。
输入输出格式
输入格式:第一行两个整数n,m。
第二行n个整数表示a[1]..a[n]。
以下m行,每行2个整数表示询问区间的左右端点。
保证输入数据合法。
输出格式:共m行,每行表示一个询问的答案。
输入输出样例
输入样例#1:5 3输出样例#1:
4 12 3 6 7
1 3
2 3
5 5
1
3
7
说明
对于30%的数据,n <= 100, m <= 10
对于60%的数据,m <= 1000
对于100%的数据,1 <= n <= 1000,1 <= m <= 1,000,000
0 < 数字大小 <= 1,000,000,000
•用f[i][j]表示ai~aj的gcd。 •f[i][i]=ai •f[i][j]=gcd(f[i][j-1],aj) (i<j) •时间复杂度O(n^2logn+m)
这里用了二进制的gcd,常数较小
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1005;
int n,m,a[MAXN],f[MAXN][MAXN];
inline int gcd(int x,int y)
{
int i,j;
if(x==0||y==0) return x+y;
for(i=0;!(x&1);i++) x>>=1;
for(j=0;!(y&1);j++) y>>=1;
if(j<i) i=j;
while(1){
if(x<y){
x^=y;y^=x;x^=y;
}
x-=y;
if(!x) return y<<i;
while(!(x&1)) x>>=1;
}
}
int main()
{
int i,j,l,r;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][i]=a[i];
}
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
f[i][j]=gcd(f[i][j-1],a[j]);
//cout<<f[i][j-1]<<' '<<a[j]<<' '<<f[i][j]<<"g";
}
}
for(i=1;i<=m;i++){
scanf("%d%d",&l,&r);
printf("%d\n",f[l][r]);
}
return 0;
}