[STEP] Problem 0132 : 汁男區間

#include<stdio.h>
#include<algorithm>
using namespace std;
long long int s[100005];
long long int dp[100005][20];
int main(){
    int n,m,i,j,x,y,t;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%lld",&s[i]);
        dp[i][0]=s[i];
    }
    for(j=1;j<=20;j++)
    for(i=0;i+(1<<j)-1<n;i++)
        dp[i][j]=__gcd(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        x--,y--;
        for(t=0;(1<<t+1)<=y-x+1;t++);
        printf("%lld\n",__gcd(dp[x][t],dp[y-(1<<t)+1][t]));
    }
}