大一寒假训练五（Gcd&Lcm）【更新完成】

本次训练共5题，本文附AC代码和题目链接。

本次训练中稍有难度的题：nefu 1221 人见人爱gcd
（难点在于数学公式的推导，得出隐含条件）

nefu 1077 最大公约数和最小公倍数 （模板题）

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}
long long lcm(long long a,long long b)
{return a/gcd(a,b)*b;}
int main()
{
    long long a,b;
    while(cin>>a>>b)
    {printf("%lld %lld\n",gcd(a,b),lcm(a,b));}
    return 0;
}

nefu 992 又见GCD

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
    int a,b,i;
    while(cin>>a>>b)
    {
        for(i=b+1;;i++)
        {
            if(gcd(a,i)==b)
            {printf("%d\n",i);break;}
        }
    }
    return 0;
}

nefu 764 多个数的最大公约数

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}
int main()
{
    long long n,i,a[11];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            cin>>a[i];
        for(i=1;i<=n-1;i++)
            a[i+1]=gcd(a[i],a[i+1]);
        printf("%lld\n",a[n]);
    }
    return 0;
}

nefu 765 多个数的最小公倍数

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}
long long lcm(long long a,long long b)
{return a/gcd(a,b)*b;}
int main()
{
    long long n,i,a[11];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            cin>>a[i];
        for(i=1;i<=n-1;i++)
            a[i+1]=lcm(a[i],a[i+1]);
        printf("%lld\n",a[n]);
    }
    return 0;
}

nefu 1221 人见人爱gcd
这题要用数学公式推导出gcd(x,y)=gcd(a,b)
从而得到 x² + y² = a²-2 * b * gcd(a,b)

推导过程如下：

AC代码：

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
    int t,a,b;
    ios::sync_with_stdio(false);
    while(cin>>t)
    {
        while(t--)
        {
            cin>>a>>b;
            printf("%d\n",a*a-2*b*gcd(a,b));
        }
    }
    return 0;
}