题解 P1029 【最大公约数和最小公倍数问题】

· · 题解

本文符号简述（大佬自行跳过）：

d|a$ : $a \% d =0 $a \in N^* $ a为自然数 $\lfloor a \rfloor$ a向下取整 $gcd(a,b)$ $a$ , $b$的最大公约数 首先，这题暴力枚举是肯定会TLE的 那么我们用什么方法呢？ 辗转相除法求gcd！ 有定理： 由 $ d|a$ 并且 $ d|b $ $ (d,a,b \in N^* )

可得 d|(xa + yb) (x,y \in Z)

证明如下：

可设xa=xk_1 d , yb=yk_2d (k_1,k_2 \in N ^ * )

\because xk_1d+yk_2d=(xk_1+yk_2)d \therefore xa +yb=(xk_1+yk_2)d \because d|(xk_1+yk_2)d \therefore d|(xa+yb)

得证。

那么怎样求gcd呢？

又有定理：

gcd(a,b)=gcd(b,a \% b) (a,b \in N^* )

证明如下：

若想证明上式，则需证明：

①.a 和 b 的任一约数都是 b 和 a \% b 的约数

②.b 和 a \% b 的任一约数都是 a 和 b 的约数

设 a 和 b 的一个约数为 c

则 c |a \& c|b

设 \lfloor \frac{a}{b} \rfloor = k

则a \% b=a-bk

\because $ $c |a $ $\&$ $c|b \therefore c | (a-bk)$ 即 $c|(a\%b)

①.得证

同理可证②.

则定理得证。

那么，求gcd就只需要递归求解，当当前a , b满足 b|a 时，gcd(a,b)=b , 否则 gcd(a,b)=gcd(b,a\%b)

实现：

inline int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}

那么问题来了，这只是最大公约数，那最小公倍数呢？

又有定理：

两个数最大公约数与最小公倍数的乘积即为这两个数的乘积

证明：

设两个数为x , y , gcd(x,y)=a , 最小公倍数为 b

设x=p_1a , y=p_2a ，由 gcd 的定义可知：p_1 与 p_2互质

\therefore$ 这互质的两数 $p_1$ , $p_2$ 最小公倍数为 $p_1p_2 \because \frac{xy}{a}=\frac{p_1* a * p_2* a}{a}=p_1p_2a 那么我说：$p_1p_2a=b

假设 p_1p_2a\not=b ：

$\therefore p_1p_2a>b

则分两种情况讨论：

  1. 若有更大的 p_1p_2 满足条件 ，则此时 a 不取最大值 ，矛盾

  2. 若有更大的 a 满足条件 ，矛盾

综上：p_1p_2a=\frac{xy}{a}=b

\therefore xy=ab

定理得证

那么此题算法也就清楚了。

枚举xy的所有因数 1 \sim \sqrt {xy},如果满足 gcd(i,\frac{xy}{i})=x , 则答案加上1。最后答案\times2即可。

#include <bits/stdc++.h>
using namespace std;
int x,y;
inline int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    cin>>x>>y;
    int ans=0;
    for(int i=1;i<=sqrt(x*y);i++)
    {
        if(x*y%i==0&&gcd(i,x*y/i)==x) ans++;
    }
    cout<<ans*2;
    return 0;
}

然后你发现错了一个点。

其实如果 \sqrt{xy} 满足条件的话，我们会重复计算。

此时， x=y

AC$ $Code 
#include <bits/stdc++.h>
using namespace std;
int x,y;
inline int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    cin>>x>>y;
    int ans=0;
    for(int i=1;i<=sqrt(x*y);i++)
    {
        if(x*y%i==0&&gcd(i,x*y/i)==x) ans++;
    }
    ans*=2;
    if(x==y) ans--;
    cout<<ans;
    return 0;
}

其实还有一点不完美，就是 x \times y 有可能会爆 int , 所以改用 long long

#include <bits/stdc++.h>
using namespace std;
long long x,y;
inline long long gcd(long long x,long long y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    cin>>x>>y;
    long long ans=0;
    for(long long i=1;i<=sqrt(x*y);i++)
    {
        if(x*y%i==0&&gcd(i,x*y/i)==x) ans++;
    }
    ans*=2;
    if(x==y) ans--;
    cout<<ans;
    return 0;
}