【CodeChef】 Gcd Queries
发布时间
阅读量：
阅读量
这段代码实现了一个高效的区间最大公约数（GCD）查询算法。通过预计算前缀GCD（lgcd）和后缀GCD（rgcd）数组，在每次查询时只需常数时间即可得到结果。具体来说：
预处理阶段：
- 读取输入数据并存储在数组a中。
- 使用一个循环计算lgcd数组：从左到右遍历数组a，并对当前元素与前缀GCD进行更新。
- 使用另一个循环计算rgcd数组：从右到左遍历数组a，并对当前元素与后缀GCD进行更新。
查询阶段：- 对于每个查询区间[L, R]，直接使用预处理得到的lgcd[L-1]和rgcd[R+1]计算结果。
该方法的时间复杂度主要取决于预处理阶段的O(N)时间和每个查询阶段的O(1)时间复杂度，整体效率较高。
#include<bits/stdc++.h>
using namespace std;
char inc;
inline void get(int& x)
{
x = 0;inc = getchar();
while(!isdigit(inc))inc=getchar();
while(isdigit(inc))
{
x=x*10+inc-'0';
inc=getchar();
}
}
#define maxn 100010
int gcd(int a,int b)
{
if(!a)return b;
if(!b)return a;
else return gcd(b,a%b);
}
int T,N,Q;
int a[maxn];
int lgcd[maxn],rgcd[maxn],L,R;
int ans[maxn];
int main()
{
get(T);
while(T--)
{
get(N),get(Q);
for(int i=1;i<=N;i++)get(a[i]);
lgcd[0] = rgcd[N+1] = 0;
for(int i=1;i<=N;i++)
lgcd[i] = gcd(lgcd[i-1],a[i]);
for(int i=N;i>=1;i--)
rgcd[i] = gcd(rgcd[i+1],a[i]);
while(Q--)
{
get(L);get(R);
printf("%d\n",gcd(lgcd[L-1],rgcd[R+1]));
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~