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

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P13014 [GESP202506 五级] 最大公因数 - 洛谷【题目描述】对于两个正整数a , b a,ba,b他们的最大公因数记为g c d ( a , b ) gcd(a,b)gcd(a,b)。对于k 3 k3k3个正整数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_1i,a_2i,…,a_nia1​i,a2​i,…,an​i的最大公因数也即g c d ( a 1 i , a 2 i , … , a n i ) gcd(a_1i,a_2i,…,a_ni)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_1i,a_2i,…,a_nia1​i,a2​i,…,an​i的最大公因数。【输入样例】5 3 6 9 12 18 30【输出样例】1 1 3【算法标签】#普及-# #约数#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义数组最大长度intn,q;// n为数组长度q为查询次数inta[N],b[N];// a存储原始数组b存储预处理结果intcur1;// 当前查询位置指针intt0;// 存储数组元素的差分GCD// 计算两个数的最大公约数intgcd(inta,intb){if(b0)returna;returngcd(b,a%b);}intmain(){// 输入数组长度和查询次数cinnq;// 输入数组元素for(inti1;in;i)cina[i];// 对数组进行排序sort(a1,a1n);// 计算相邻元素的差分GCDfor(inti2;in;i)tgcd(t,a[i]-a[i-1]);// 处理所有元素相同的情况差分为0if(t0){for(inti1;iq;i)couta[i]iendl;return0;}// 预处理每个偏移量i的GCD结果for(inti1;it;i){intg0;for(intj1;jn;j)ggcd(g,a[j]i);b[i]g;}// 处理查询for(inti1;iq;i){coutb[cur]endl;cur;if(curt)cur1;// 循环使用预处理结果}return0;}【运行结果】5 3 6 9 12 18 30 1 1 3