小红的gcd【牛客tracker 每日一题】

小红的gcd

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红有一个长度为n nn的数组，她希望数组元素之和越少越好。
她可以进行任意次操作，每次选择数组中的两个元素a i a_iai​​ 和a j a_jaj​，令a i = a j = g c d ⁡ ( a i , a j ) a_i=a_j=gcd⁡(a_i,a_j)ai​=aj​=gcd⁡(ai​,aj​)。
所有操作结束后，请你输出最小的数组元素之和。

输入描述：

第一行有一个整数n ( 1 ≤ n ≤ 10 5 ) n ( 1≤n≤10^5 )n(1≤n≤105)。
第二行有n nn个整数a i ( 1 ≤ a i ≤ 10 9 ) a_i ( 1≤a_i≤10^9 )ai​(1≤ai​≤109)。

输出描述：

输出一个整数，代表最小的数组元素之和 。

示例1

输入：

5 2 4 6 8 10

输出：

10

解题思路

核心先推导操作的本质规律，每次将两个数替换为其最大公约数的操作，可不断缩小数组元素值，且所有操作后数组所有元素的公共约数始终等于原数组的整体最大公约数g gg，而通过任意次操作能将所有元素都变为g（这是操作后能得到的最小元素值，无法比整体g c d gcdgcd更小）；因此解题时只需遍历数组计算所有元素的整体g c d gcdgcd，若n = 1 n=1n=1则最小和为数组唯一元素，否则最小和为n nn乘以该整体g c d gcdgcd；该方法遍历求整体g c d gcdgcd的时间复杂度为O ( n log ⁡ m a x ( a i ) ) O(n \log max(a_i))O(nlogmax(ai​))，无任何冗余计算，完美适配n ≤ 1 e 5 、 a i ≤ 1 e 9 n≤1e5、a_i≤1e9n≤1e5、ai​≤1e9的规模，直接通过整体g c d gcdgcd推导最小和，精准满足“元素之和越少越好”的要求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;intmain(){ll n;cin>>n;vector<ll>a(n+1,0);for(ll i=1;i<=n;i++){cin>>a[i];a[1]=gcd(a[i],a[1]);}cout<<n*a[1]<<endl;return0;}