P1890gcd区间(爱思创题解)-创新互联
gcd区间
题目描述
分享名称:P1890gcd区间(爱思创题解)-创新互联
网址分享:http://myzitong.com/article/dpdheo.html
给定一行n个正整数a[1]…a[n]。
创新互联建站成立十年来,这条路我们正越走越好,积累了技术与客户资源,形成了良好的口碑。为客户提供成都网站建设、成都网站制作、网站策划、网页设计、申请域名、网络营销、VI设计、网站改版、漏洞修补等服务。网站是否美观、功能强大、用户体验好、性价比高、打开快等等,这些对于网站建设都非常重要,创新互联建站通过对建站技术性的掌握、对创意设计的研究为客户提供一站式互联网解决方案,携手广大客户,共同发展进步。m次询问,每次询问给定一个区间[L,R]
,输出a[L]~a[R]
的大公因数。
第一行两个整数n,m。
第二行n个整数表示a[1]…a[n]。
以下m行,每行2个整数表示询问区间的左右端点。
保证输入数据合法。
输出格式共m行,每行表示一个询问的答案。
样例 #1 样例输入 #15 3 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
思路我们看题不难发现题目是寻找a[L]~a[R]
这片区间之内的一个最值问题。不过这题中是求区间内的大公因数,区间!所以,要求:多次求解连续区域
a
∼
b
a\sim b
a∼b 的大公因数。我们能想到什么?很明显!求区间最值问题的ST表,ST表不懂的看这里。
#includeusing namespace std;
typedef long long ll;
const int N = 100010;
int maxn[N][50]; //区间大值表
int lg[N]; //lg函数,其实就是课上讲的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去倍增区间长度的
lg[i] = lg[i/2] + 1;
}
for(int i = 1;i<=lg[n];i++) //建立st表,第一维是区间起始位置,第二维终止位置是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];
//查询,求两个子区间的并集,,第二个区间的左端点,这个端点我们不知道
//就假设它为x,那么x + (1<
GCD求法while
循环b!=0
,使用辗转相除法
int gcd(int a,int b)
{int r=a%b;
while(r>0)
{a=b;
b=r;
r=a%b;
}
return b;
}
2.使用递归,还是辗转相除法
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<
禁止抄袭!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享名称:P1890gcd区间(爱思创题解)-创新互联
网址分享:http://myzitong.com/article/dpdheo.html