原本可以10分鐘寫完的QAQ 竟然卡__gcd
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<iostream> using namespace std; #define N 100000 int a[N]; int gcdTree[4*N]; int base; int n; int gcd(int a,int b) { if(a*b==0) return a+b; if(b>a) a^=b^=a^=b; if(a%b==0) return b; return gcd(b,a%b); } void BuildTree() { base=(int)pow(2,ceil(log2(n)))-1; if(base==(n-1)) base=base*2+1; for(int lx=0;lx<n;lx++) gcdTree[lx+base+1]=a[lx]; for(int lx=base;lx;lx--) gcdTree[lx]=gcd(gcdTree[lx*2],gcdTree[lx*2+1]); } int Ask(int a,int b) { int re=0; for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1) { if(~a&1) re=gcd(re,gcdTree[a^1]); if(b&1) re=gcd(re,gcdTree[b^1]); } return re; } int main() { int q; scanf("%d %d",&n,&q); for(int lx=0;lx<n;lx++) scanf("%d",&a[lx]); BuildTree(); int a,b; while(q--) { scanf("%d %d",&a,&b); printf("%d\n",Ask(a,b)); } return 0; }
沒有留言:
張貼留言