kldxx定理定义：对于非负整数a、b，由于存在x、y，ax by=gcd(a，b )，也就是说axby能够构成的最小正整数是gcd (a，b )。 (a,b不同时为0) )注意
不难理解，练习一道题吧
模板kldxx定理
设想：要求A1 * x1 A2 * x2 A3 * X3… An * Xn=S
要求最小的s
只要重复下去就行了
因为a1*x1A2*x2=gcd(a1，a2 )
迭代得到(A1 * x1 A2 * x2 ) A3*x3=gcd ) gcd(a1，A2 )，a3 )
这样反复进行，求最后，也就是A1、A2、A3…An所有数的最大公约数
这里有详细内容的是S0，所以需要将所有Ai转换为正数
AC代码如下
# include iostream # include cmath # includealgorithmusingnamespacestd； int main () {int n； scanf('%d '，n )； int a[n 5]； a[0]=0； for(intI=1； i=n； I ) Scanf('%d '，a[i]； a[I]=ABS(a[I]； (intgcd=) a[1]，a[1]； for(intI=2； i=n； I ) ) gcd=__gcd(gcd，a[i]； }printf('%d”，gcd )； 返回0； }