这道题的题目描述:
题目描述
给定一行n个正整数a[1]..a[n]。
m次询问,每次询问给定一个区间[L,R],输出a[L]..a[R]的最大公因数。
输入输出格式
输入格式:
第一行两个整数n,m。
第二行n个整数表示a[1]..a[n]。
以下m行,每行2个整数表示询问区间的左右端点。
保证输入数据合法。
输出格式:
共m行,每行表示一个询问的答案。
输入输出样例
输入样例#1:
5 3
4 12 3 6 7
1 3
2 3
5 5
输出样例#1:
1
3
7
不说这么多,题目描述就是这样
做这道题,可以大致分为这样几个步骤:
1.输入
2.处理
3.query
4.每次3后愉快输出
5.return 0 ;
emmm,代码就不复制了,
我直接手打一份吧!
(错了就不要怪我了呦!!)
首先是输入
scanf("%lld%lld",&n,&m) ;
for(int i = 1 ; i <= n ; i ++){
scanf("%lld",&a[i]) ;
呵呵,.......................
啥?后括号呢?管***啥?是吧?/xyx
然后是预处理
由于数据中会有一些l == r 的数据
所以我们索性::
f[i][i] = a[i] ;
}
for(int i = 1 ; i <= n ; i ++ )
for(int j = i+1 ; j <= n ; j ++){
f[i][j] = gcd(f[i][j-1],a[j]) ;
}
然后就是query+输出+return 0 :
这个真的没啥可说的啊
while(m --){
int r , l ;
scanf("%lld%lld",&r,&l) ;
printf("%lld",f[r][l]) ;
//return 0 ; //开玩笑的
}
return 0 ;
然后就是前置的一些东西了
#define int long long
//这就是我int r,l 却scanf("%lld")的原因了!
using namespace std ;//这里我们........
int gcd(int a , int b){
return b == 0 ? a : gcd(b,a%b) ;
}
signed main()/*这里比较重要,signed <=> int*/{
}
完结!!!!!!
等等,我还是在贴个完整代码吧
所谓完整代码其实也就是把上面的各个部分有机的拼合啊
#include<iostream>
#include<stdio.h>
#include<string.h>
#define maxn 2000
#define int long long
using namespace std ;
int gcd(int a,int b){
return b == 0 ? a : gcd(b,a%b) ;
}
int n , m ;
int a[maxn] ;
int f[maxn][maxn] ;
signed main(){
scanf("%lld%lld",&n,&m) ;
for(int i = 1 ; i <= n ; i ++){
scanf("%lld",&a[i]) ;
f[i][i] = a[i] ;
}
for(int i = 1 ; i <= n ; i ++)
for(int j = i+1 ; j <= n ; j ++){f[i][j] = gcd(f[i][j-1],a[j]) ;}
while(m --){
int l , r ;
scanf("%lld%lld",&r,&l) ;
printf("%lld\n",f[r][l]) ;
}
}
return 0 ;
return 0 ;