給定一行n個正整數(shù)a[1]…a[n]。
創(chuàng)新互聯(lián)建站成立十年來,這條路我們正越走越好,積累了技術與客戶資源,形成了良好的口碑。為客戶提供成都網站建設、成都網站制作、網站策劃、網頁設計、申請域名、網絡營銷、VI設計、網站改版、漏洞修補等服務。網站是否美觀、功能強大、用戶體驗好、性價比高、打開快等等,這些對于網站建設都非常重要,創(chuàng)新互聯(lián)建站通過對建站技術性的掌握、對創(chuàng)意設計的研究為客戶提供一站式互聯(lián)網解決方案,攜手廣大客戶,共同發(fā)展進步。m次詢問,每次詢問給定一個區(qū)間[L,R]
,輸出a[L]~a[R]
的大公因數(shù)。
第一行兩個整數(shù)n,m。
第二行n個整數(shù)表示a[1]…a[n]。
以下m行,每行2個整數(shù)表示詢問區(qū)間的左右端點。
保證輸入數(shù)據合法。
輸出格式共m行,每行表示一個詢問的答案。
樣例 #1 樣例輸入 #15 3 4 12 3 6 7 1 3 2 3 5 5
1 3 7
對于30%的數(shù)據,n<= 100, m<= 10
對于60%的數(shù)據,m<= 1000
對于100%的數(shù)據,1<= n<= 1000,1<= m<= 1,000,000
0< 數(shù)字大小<= 1,000,000,000
思路我們看題不難發(fā)現(xiàn)題目是尋找a[L]~a[R]
這片區(qū)間之內的一個最值問題。不過這題中是求區(qū)間內的大公因數(shù),區(qū)間!所以,要求:多次求解連續(xù)區(qū)域
a
~
b
a\sim b
a~b 的大公因數(shù)。我們能想到什么?很明顯!求區(qū)間最值問題的ST表,ST表不懂的看這里。
#includeusing namespace std;
typedef long long ll;
const int N = 100010;
int maxn[N][50]; //區(qū)間大值表
int lg[N]; //lg函數(shù),其實就是課上講的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去倍增區(qū)間長度的
lg[i] = lg[i/2] + 1;
}
for(int i = 1;i<=lg[n];i++) //建立st表,第一維是區(qū)間起始位置,第二維終止位置是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];
//查詢,求兩個子區(qū)間的并集,,第二個區(qū)間的左端點,這個端點我們不知道
//就假設它為x,那么x + (1<
GCD求法while
循環(huán)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<
禁止抄襲!
你是否還在尋找穩(wěn)定的海外服務器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源,準確流量調度確保服務器高可用性,企業(yè)級服務器適合批量采購,新人活動首月15元起,快前往官網查看詳情吧
網頁名稱:P1890gcd區(qū)間(愛思創(chuàng)題解)-創(chuàng)新互聯(lián)
網頁網址:http://muchs.cn/article40/dpdheo.html
成都網站建設公司_創(chuàng)新互聯(lián),為您提供電子商務、定制網站、網站設計、動態(tài)網站、品牌網站制作、靜態(tài)網站
聲明:本網站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內容