首页 > 代码库 > 洛谷P1890 gcd区间 [2017年6月计划 数论09]
洛谷P1890 gcd区间 [2017年6月计划 数论09]
P1890 gcd区间
题目描述
给定一行n个正整数a[1]..a[n]。
m次询问，每次询问给定一个区间[L,R]，输出a[L]..a[R]的最大公因数。
输入输出格式
输入格式：
第一行两个整数n，m。
第二行n个整数表示a[1]..a[n]。
以下m行，每行2个整数表示询问区间的左右端点。
保证输入数据合法。
输出格式：
共m行，每行表示一个询问的答案。
输入输出样例
输入样例#1：
5 34 12 3 6 71 32 35 5
输出样例#1：
137
说明
对于30%的数据，n <= 100， m <= 10
对于60%的数据，m <= 1000
对于100%的数据，1 <= n <= 1000，1 <= m <= 1,000,000
满足区间加法，询问远大于数据量，st表最快
#include <cstdio>#include <iostream>#include <cstring>const int MAXN = 1000 + 10;inline void read(long long& x){ x = 0;char ch = getchar();char c = ch; while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar(); while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar(); if(c == ‘-‘)x = -x;}inline int min(long long a, long long b){return a > b ? a : b;}inline int max(long long a, long long b){return a > b ? b : a;}long long stlist[MAXN][30];long long num[MAXN];long long log2[MAXN]; long long pow2[MAXN];long long n,m;inline int gcd(int a, int b){ if(a < b) { int tmp = a; a = b; b = tmp; } while(b) { int tmp = a % b; a = b; b = tmp; } return a;}void yuchuli(){ int M = 0; while(pow2[M + 1] <= n)M ++; for(int i = 1;i <= M;i ++) { for(int j = n;j > 0;j --) { stlist[j][i] = stlist[j][i - 1]; if(j + pow2[i - 1] <= n)stlist[j][i] = gcd(stlist[j + pow2[i - 1]][i - 1], stlist[j][i]); } }}int stfind(int l, int r){ int M = 0; while(pow2[M + 1] <= (r - l + 1))M ++; return gcd(stlist[l][M], stlist[r - pow2[M] + 1][M]);} long long tmp1, tmp2;int main(){ read(n);read(m); for(int i = 1;i <= n;i ++) read(stlist[i][0]); log2[0] = -1; for(int i = 1;i <= n;i ++) log2[i] = log2[i >> 1] + 1; pow2[0] = 1; for(int i = 1;i <= n;i ++) pow2[i] = pow2[i - 1] << 1; yuchuli(); for(int i = 1;i <= m;i ++) { read(tmp1);read(tmp2); printf("%d\n", stfind(tmp1, tmp2)); } return 0;}
洛谷P1890 gcd区间 [2017年6月计划 数论09]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。