AT_ddcc2017_final_b GCDロボット 题解

Wy_x · 2022-10-20 12:01:17 · 题解

题目传送门

更好的阅读体验？

• 求最大公因数与最小公倍数的一道好题。

做法：

• 和 z“完全一样”的数，就是每个机器人里的数与 z 的最大公因数的最小公倍数。

• 求最大公因数可以使用辗转相除法，也可以使用 \texttt{STL} 中的求最大公约数的函数，在 std 命名空间里，写法为 __gcd(x,y)，可以直接用，不用手写了。

• 最小公倍数为两数的乘积除以两数的最大公因数。

提示：

• 数据范围到了 {10}^{18}，需要开 long long。

• 如果你 UKE，你可以重新提交一次。

提供三种代码：

1. 压行代码：

#include<cstdio>//不用万能头可以提速 
long long gcd(long long x,long long y) { return y==0?x:gcd(y,x%y); } //最大公约数函数 
long long n,z,a[100005],ans=1;
int main()//压一压行 
{
    scanf("%lld%lld",&n,&z);
    for(register int i=1;scanf("%lld",&a[i])&&i<=n;i++)  ans=ans/gcd(ans,gcd(a[i],z))*gcd(a[i],z);
    printf("%lld\n",ans);
    return 0;
}

2. 不压行代码：

#include<cstdio>
long long gcd(long long x,long long y) { return y==0?x:gcd(y,x%y); } //最大公约数函数 
long long n,z,a[100005],ans=1;
int main()
{
    scanf("%lld%lld",&n,&z);
    for(register int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        long long nw=gcd(a[i],z);
        ans=ans/(gcd(ans,nw))*nw;
    }
    printf("%lld\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long n,z,a[100005],ans=1;
int main()
{
    scanf("%lld%lld",&n,&z);
    for(register int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        long long nw=__gcd(a[i],z);//stl里的函数
        ans=ans/(__gcd(ans,nw))*nw;
    }
    printf("%lld\n",ans);
    return 0;
}