当前位置：首页 > news >正文

题解：洛谷 P13014 [GESP202506 五级] 最大公因数

news 2026/5/8 22:49:57

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P13014 [GESP202506 五级] 最大公因数 - 洛谷

【题目描述】

对于两个正整数a , b a,ba,b，他们的最大公因数记为g c d ( a , b ) gcd(a,b)gcd(a,b)。对于k > 3 k>3k>3个正整数c 1 , c 2 , … , c k c_1,c_2,…,c_kc1,c2,…,ck，他们的最大公因数为：

g c d ( c 1 , c 2 , … , c k ) = g c d ( g c d ( c 1 , c 2 , … , c k − 1 ) , c k ) gcd(c_1,c_2,…,c_k)=gcd(gcd(c_1,c_2,…,c_{k−1}),c_k)gcd(c1,c2,…,ck)=gcd(gcd(c1,c2,…,ck−1),ck)

给定n nn个正整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1,a2,…,an以及q qq组询问。对于第i ( 1 ≤ i ≤ q ) i(1≤i≤q)i(1≤i≤q)组询问，请求出a 1 + i , a 2 + i , … , a n + i a_1+i,a_2+i,…,a_n+ia1+i,a2+i,…,an+i的最大公因数，也即g c d ( a 1 + i , a 2 + i , … , a n + i ) gcd(a_1+i,a_2+i,…,a_n+i)gcd(a1+i,a2+i,…,an+i)。

【输入】

第一行，两个正整数n , q n,qn,q，分别表示给定正整数的数量，以及询问组数。

第二行，n nn个正整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1,a2,…,an。

【输出】

输出共q qq行，第i ii行包含一个正整数，表示a 1 + i , a 2 + i , … , a n + i a_1+i,a_2+i,…,a_n+ia1+i,a2+i,…,an+i的最大公因数。

【输入样例】

5 3 6 9 12 18 30

【输出样例】

1 1 3

【算法标签】

#普及-# #约数#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 定义数组最大长度intn,q;// n为数组长度，q为查询次数inta[N],b[N];// a存储原始数组，b存储预处理结果intcur=1;// 当前查询位置指针intt=0;// 存储数组元素的差分GCD// 计算两个数的最大公约数intgcd(inta,intb){if(b==0)returna;returngcd(b,a%b);}intmain(){// 输入数组长度和查询次数cin>>n>>q;// 输入数组元素for(inti=1;i<=n;i++)cin>>a[i];// 对数组进行排序sort(a+1,a+1+n);// 计算相邻元素的差分GCDfor(inti=2;i<=n;i++)t=gcd(t,a[i]-a[i-1]);// 处理所有元素相同的情况（差分为0）if(t==0){for(inti=1;i<=q;i++)cout<<a[i]+i<<endl;return0;}// 预处理每个偏移量i的GCD结果for(inti=1;i<=t;i++){intg=0;for(intj=1;j<=n;j++)g=gcd(g,a[j]+i);b[i]=g;}// 处理查询for(inti=1;i<=q;i++){cout<<b[cur]<<endl;cur++;if(cur>t)cur=1;// 循环使用预处理结果}return0;}