P1890 gcd区间
我一开始80分
暴力，模拟
100做法
dp
O(n^2+m)
f[i][j]表示i到j的 gcd
初始化
f[i][i]=i;
f[i][j]=gcd(f[i][j-1],a[j]);
这样查询就到了O(1)
80代码
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define p(a) putchar(a) #define g() getchar() #define inf 2147483647 #define For(i,a,b) for(register int i=a;i<=b;i++) using namespace std; void in(int &x) { int y=1; char c=g();x=0; while(c<‘0‘||c>‘9‘) { if(c==‘-‘) y=-1; c=g(); } while(c<=‘9‘&&c>=‘0‘)x=x*10+c-‘0‘,c=g(); x*=y; } void o(int x) { if(x<0) { p(‘-‘); x=-x; } if(x>9)o(x/10); p(x%10+‘0‘); } int gcd(int a,int b) { return (b==0?a:gcd(b,a%b)); } int n,m; int a[1010]; int l,r,g; int main() { in(n),in(m); For(i,1,n) in(a[i]); For(i,1,m) { in(l),in(r); g=a[l]; For(j,l+1,r) g=gcd(g,a[j]); o(g),p(‘\n‘); } return 0; }
100分
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define p(a) putchar(a) #define g() getchar() #define inf 2147483647 #define For(i,a,b) for(register int i=a;i<=b;i++) using namespace std; void in(int &x) { int y=1; char c=g();x=0; while(c<‘0‘||c>‘9‘) { if(c==‘-‘) y=-1; c=g(); } while(c<=‘9‘&&c>=‘0‘)x=x*10+c-‘0‘,c=g(); x*=y; } void o(int x) { if(x<0) { p(‘-‘); x=-x; } if(x>9)o(x/10); p(x%10+‘0‘); } int gcd(int a,int b) { return (b==0?a:gcd(b,a%b)); } int n,m; int a[1010]; int l,r,g; int f[1010][1010]; int main() { in(n),in(m); For(i,1,n) in(a[i]); For(i,1,n) f[i][i]=a[i]; For(i,1,n) For(j,i+1,n) f[i][j]=gcd(f[i][j-1],a[j]); For(i,1,m) { in(l),in(r); o(f[l][r]),p(‘\n‘); } return 0; }
原文：http://www.cnblogs.com/war1111/p/7632850.html