本文共 2096 字，大约阅读时间需要 6 分钟。

目录

欧几里得算法

专门算两个数的最大公约数的算法，又称辗转相除法。即 gcd(a,b) = gcd(b,a%b)。很明显，边界是b = 0，返回a。

gcd(int a,int b) {    return b == 0 ? a : gcd(b,a % b);}

最大公约数

题目描述

已知N个数a1~an，这N个数的乘积为A,又已知M个数b1~bm，这M个数的乘积为B。求A,B的最大公约数。如果其最大公约数超过9位，则只需输出最后9位。

输入

第一行一个整数N.（1<=N<=1000）

第三行一个整数M(1<=M<=1000)

输出

一个整数，即A,B的最大公约数。若超过9位，则只输出9位。

样例输入

Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)

32 3 524 5

样例输出

10

分析+代码

这道题数据很大，光用longlong还不行，每次乘法后都要取模，但是取模后就不能用gcd()了，这可怎么办呢？

还是要用唯一分解定理，但是已经没嫩么重要了。从题目中得知，A和B都是极大的整数（），不方便用高精，就不能直接求gcd(A,B)。

我们看，输入中已经把A和B都分成了各个整数的积，相当于在A，B的唯一分解中，已经分成了若干小块。

两个整数如果都除以它们的最大公约数，它们的唯一分解中就没有重复的，就是互质数，那时，A的因子的分解中也肯定没有与B的任意因子分解重合的部分，所以到那时，a1~an中的每一个数都与b1~bm中每一个数互质。这个把A，B转为互质数的过程，就可以代替为把A，B分解的因数（a1~an和b1~bm）每一对（ai和bj）都转为互质。不难发现，一共有n*m次gcd()计算。在每一次计算gcd(ai,bj)时记录下gcd，最后求积就行。

最后是代码（要对自己负责！）：

#include
   
    #include
    
     #include
     
      #include
      
       #define LL long long#define max(x,y) (x > y ? x : y)#define min(x,y) (x < y ? x : y)using namespace std;LL read() {    LL f = 1,x = 0;char s = getchar();    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}    return x * f;}LL a[1005],b[1005];bool fl = 0;LL n,m,i,j,k,s,o,num;LL gcd(LL x,LL y) {    return y == 0? x : gcd(y,x % y);}int main() {    n = read();    for(i = 1;i <= n;i ++) {        a[i] = read();    }    m = read();    for(i = 1;i <= m;i ++) {        b[i] = read();    }    LL ans = 1;    for(i = 1;i <= n;i ++) {        for(j = 1;j <= m;j ++) {            s = gcd(a[i],b[j]);            a[i] /= s,b[j] /= s;            ans *= s;            if(ans > 1000000000) fl = 1,ans %= 1000000000;//当answer超过10^9时,要输出前导零        }    }    if(fl && ans < 100000000) putchar('0');    if(fl && ans < 10000000) putchar('0');    if(fl && ans < 1000000) putchar('0');    if(fl && ans < 100000) putchar('0');    if(fl && ans < 10000) putchar('0');    if(fl && ans < 1000) putchar('0');    if(fl && ans < 100) putchar('0');    if(fl && ans < 10) putchar('0');    printf("%lld",ans);    return 0;}
      
     
    
   

下一篇：

转载地址：https://blog.csdn.net/weixin_43960414/article/details/88180241 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！