P1890gcd區(qū)間(愛思創(chuàng)題解）-創(chuàng)新互聯(lián)

給定一行n個正整數(shù)a[1]…a[n]。

m次詢問，每次詢問給定一個區(qū)間[L,R]，輸出a[L]~a[R]的大公因數(shù)。

第一行兩個整數(shù)n，m。

第二行n個整數(shù)表示a[1]…a[n]。

以下m行，每行2個整數(shù)表示詢問區(qū)間的左右端點。

保證輸入數(shù)據(jù)合法。

共m行，每行表示一個詢問的答案。

5 3 4 12 3 6 7 1 3 2 3 5 5

1 3 7

對于30%的數(shù)據(jù)，n<= 100， m<= 10

對于60%的數(shù)據(jù)，m<= 1000

對于100%的數(shù)據(jù)，1<= n<= 1000，1<= m<= 1,000,000

0< 數(shù)字大小<= 1,000,000,000

我們看題不難發(fā)現(xiàn)題目是尋找a[L]~a[R]這片區(qū)間之內(nèi)的一個最值問題。不過這題中是求區(qū)間內(nèi)的大公因數(shù)，區(qū)間！所以，要求：多次求解連續(xù)區(qū)域 a ～ b a\sim b a～b 的大公因數(shù)。我們能想到什么？很明顯！求區(qū)間最值問題的ST表,ST表不懂的看這里。

#includeusing namespace std;

typedef long long ll;
const int N = 100010;

int maxn[N][50];    //區(qū)間大值表
int lg[N];  //lg函數(shù),其實就是課上講的Log[N]

inline int read(){//快速輸入
    int x = 0,f=1;char ch = getchar();
    while(ch< '0' || ch >'9') {if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch<= '9'){x = x*10 + ch - '0'; ch = getchar();}
    return x*f;
}

int main(){int n,m;
    n = read(); m = read();

    for(int i = 1;i<=n;i++){//初始化
        maxn[i][0] = read();
    }

    for(int i = 2;i<=n;i++){//以2為底的lg求出來 ,最少要求到lgn，因為我們是通過2^i去倍增區(qū)間長度的
        lg[i] = lg[i/2] + 1;
    }

    for(int i = 1;i<=lg[n];i++)     //建立st表，第一維是區(qū)間起始位置，第二維終止位置是2^i-1
        for(int j = 1;j + (1<maxn[j][i] = max(maxn[j][i-1],maxn[j+(1<<(i-1))][i-1]);
        }

    int l,r;
    while(m--){l = read(); r = read();

        int len = lg[r-l+1];

        //查詢，求兩個子區(qū)間的并集，，第二個區(qū)間的左端點，這個端點我們不知道
        //就假設它為x，那么x + (1<

int gcd(int a,int b)
{int r=a%b;
	while(r>0)
	{a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);//遞歸+三目運算符
}

#includeusing namespace std;
const int N = 1e5+5;
int st[N][20];
int logg[N];
int n,m;
int gcd(int a,int b)
{if(b==0) return a;
	else return gcd(b,a%b);	
} 
int main()
{	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){scanf("%d",&st[i][0]);
	}
	for(int i=2;i<=n;i++) logg[i]=logg[i/2]+1;
	
	for(int j=1;j<=logg[n];j++){for(int i=1;i+(1<	st[i][j]=gcd(st[i][j-1],st[i+(1<scanf("%d%d",&l,&r);
		int x=logg[r-l+1];
		printf("%d\n",gcd(st[l][x],st[r-(1<