第 178 场双周赛Q2：101005. 数对的最大公约数之和
题目链接：101005. 数对的最大公约数之和（中等）
算法原理：
解法：模拟
92ms击败12.06%
时间复杂度O(n⋅logn)
模拟思路很简单：
①按题意构造prefixGcd数组：一个for循环解决
②给prefixGcd数组排序：Arrays.sort(prefixGcd)解决
③封装找最大公约数的方法：之前做过类似题目如下👇
D.二分查找－二分答案－第K小/第K大——878. 第 N 个神奇数字
A.每日一题——2654. 使数组所有元素变成 1 的最少操作次数
D.二分查找－二分答案－第K小/第K大——1201. 丑数 III
写法有循环法和递归法两种，我们任选一种即可
④首尾两数两两配对，将二者的gcd累加进结果：经典的双指针模型：对撞双指针👇
一轮复习——B.双指针模型总结
优化
69ms击败89.36%
时间复杂度O(n⋅logn)
①GCD 实现（首要原因）
迭代版（int 版）：纯 while 循环，无函数调用 / 栈帧开销，指令紧凑
递归版（long 版）：每次调用创建 / 销毁栈帧（Java 无尾递归优化），多次调用开销累积
②数据类型（次要原因）
int（4 字节）：CPU 缓存命中率高，算术运算（%/max）更高效
long（8 字节）：缓存命中率低，运算 / 内存操作耗时翻倍
③排序 / 转换（细节补充）
Arrays.sort(int[]) 比 sort(long[]) 比较 / 交换开销更小
long 版存在 int→long 隐式转换，迭代版无此冗余
Java代码：
class Solution { public long gcdSum(int[] nums) { int n=nums.length; long[] prefixGcd=new long[n]; long mxi=0; for(int i=0;i<n;i++){ mxi=Math.max(mxi,nums[i]); prefixGcd[i]=gcd(nums[i],mxi); } Arrays.sort(prefixGcd); long ret=0; int left=0,right=n-1; while(left<right){ ret+=gcd(prefixGcd[left],prefixGcd[right]); left++; right--; } return ret; } //获取最大公约数 private long gcd(long a,long b){ return b==0?a:gcd(b,a%b); } }class Solution { //优化 public long gcdSum(int[] nums) { int n=nums.length; int[] prefixGcd=new int[n]; int mxi=0; for(int i=0;i<n;i++){ mxi=Math.max(mxi,nums[i]); prefixGcd[i]=gcd(nums[i],mxi); } Arrays.sort(prefixGcd); long ret=0; int left=0,right=n-1; while(left<right){ ret+=gcd(prefixGcd[left],prefixGcd[right]); left++; right--; } return ret; } //获取最大公约数 private int gcd(int a,int b){ while(a!=0){ int tmp=a; a=b%a; b=tmp; } return b; } }