526互联

最大公约数与最小公倍数

发布时间 2023-12-04 09:50:50作者: 加固文明幻景

最大公约数与最小公倍数

定义

  • 对于两个整数 \(a_1,a_2\)，如果 \(d|a_1, d|a_2\)，那么 \(d\) 就称为 \(a_1,a_2\) 的公约数，其中最大的称为 \(a_1,a_2\) 的最大公约数，记作 \((a_1,a_2)\)。一般地，可以类似地定义 \(k\) 个整数 \(a_1,a_2,\dots ,a_k\) 的公约数和最大公约数，后者记作 \((a_1,\dots ,a_k)\)。

  • 对于两个整数 \(a_1,a_2\)，如果 \(a_1|l, a_2|l\)，那么 \(l\) 就称为 \(a_1,a_2\) 的公倍数，其中最小的称为 \(a_1,a_2\) 的最小公倍数，记作 \([a_1,a_2]\)。一般地，可以类似地定义 \(k\) 个整数 \(a_1,a_2,\dots ,a_k\) 的公倍数和最小公倍数，后者记作 \([a_1,\dots ,a_k]\)。

性质

  1. 对于任意整数 \(m\)，\(m(a_1,\dots,a_k) = (ma_1,\dots,ma_k)\)，即整数同时成倍放大，最大公约数也放大相同倍数，该结论同样适用于最小公倍数。

  2. 对于任意整数 \(x\) ，\((a_1, a_2) = (a_1, a_2 + a_1x)\)，即一个整数加上另一个整数的任意倍数，它们的最大公约数不变。该性质不适用于最小公倍数。

    \[(16,10) = (16 - 10, 10) = (6, 10) = (6,10-6)=(6,4)=(6-4,4)=(2,4)=(2,4-2\times2) = (2,0) = 2 \]

    \[(a,0) =a \]

  3. \((a_1,a_2,a_2,\dots,a_k) = ((a_1,a_2),a_3,\dots,a_k)\)，以及一个显然的推论 \((a_1,a_2,a_3,\dots,a_{k+r}) = ((a_1,\dots,a_k)(a_{k + 1},\dots,a_{k+r}))\)。该结论同样适用于最小公倍数。

    1. 这是计算多元最大公约数的主要手段。
    2. \((12,18,21) = ((12,18),21) = (6,21) = 3\)
    3. 说明了最大公约数的运算具备某种”结合律“。

  4. \([a_1,a_2](a_1,a_2) = a_1a_2\)，最大公约数 \(\times\) 最小公倍数 \(=\) 原来两个数的乘积。

辗转相除法

利用性质2.可以给出一个高效计算两数最大公约数的算法：每次让较大的数对较小的数取模（相当于较大数减去了若干倍较小数，最高效地运用了性质2.，而且运用模运算不必区分两数大小），可以缩小问题规模而保持最大公约数不变，然后重复这个步骤。直到其中一个数变成 \(0\) ，那么另一个数即为答案。

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

最坏情况下时间复杂度为 \(\operatorname O(\log{\max(x,y)})\)。

值得注意的是，相近规模下能让辗转相除法执行次数最多的数是相邻的两个斐波那契数，对于绝大多数情况，辗转相除法的时间可以忽略不计。

压行简化版：

int gcd(int x, int y){return y ? gcd(y, x % y): x;}

再利用性质4.，用两数之积除去最大公约数便得到了最小公倍数。

int lcm(int x, int y){return x/gcd(x,y)*y;}

因为 \(x\) 一定是 \(\gcd(x,y)\) 的倍数，所以这样先除后乘没有问题，而且可以避免可能的溢出时间。

例题

我们可以枚举 \(x\)，判断是否存在满足条件 \(1\) 的整数 \(y\)（即，\(x\) 能否被 \(P,Q\) 的积整除）。满足第一个条件后，再分别判断当前的 \(x,y\) 是否能够同时满足另外两个条件即可。显然，这种做法会超时。

考虑优化这个程序。我们其实并不需要枚举两次，因为对于不同的 \(x,y\) ，交换它们的值一定可以得到另一组与之对应的解。因此，从 \(1\) 到 \(\sqrt{P\times Q}\) 枚举一遍，每发现一组答案就将 \(ans\) 的值加上 \(2\) 即可。

一组 \(x,y\) 有对应解时有条件：\(x,y\) 的值不同。如果它们相同，交换后并不能得到与之对应的另一组数。当 \(x=y\) 时，易得 \(x=y=\gcd(x,y)=\operatorname{lcm}(x,y)\)。
所以要对此进行特判，若 \(P,Q\) 相等，这种情况就存在， \(ans\) 里要减去 \(1\)。

由性质4.当积相同且 \(\gcd\) 相同时，\(\operatorname{lcm}\) 也一定相同，因此只需判断是否满足一、二两个条件即可。

代码中为什么枚举到 \(\sqrt{n}\) 避免重复，因此循环时只算 \(x\le y\) 的情况。当 \(x=y\) 时，\(x=\sqrt{n}\)。再使 \(x\) 变大就会使 \(x>y\) 了，计算会重复。

#include<bits/stdc++.h>
using namespace std;
long long m,n,ans;
int main(){
	cin>>m>>n;
	if(m==n) ans--;
	n*=m;//把两数的积存入n中 
	for(long long i=1;i<=sqrt(n);i++){
		if(n%i==0&&__gcd(i,n/i)==m) ans+=2;
	}
	cout<<ans;
	return 0;
}

与上题类似，枚举一个数的约数再检验即可。

#include<iostream>
#include<algorithm>
#include<cstdio>

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y) {
	return x / gcd(x,y) * y;
}

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t;
	std::cin >> t;
	while(t--)
	{
		int a0, a1, b0, b1;
		int cnt = 0;
		std::cin >> a0 >> a1 >> b0 >> b1;
		for (int x = 1; x * x <= b1; x ++)//仍然用枚举到平方根的枚举约数的技巧
		{
			if (b1 % x == 0)
			{
				if (gcd(x, a0) == a1 && lcm(x, b0) == b1) ++ cnt;
				if (b1/x != x)//避免重复 
				{
					if (gcd(b1/x, a0) == a1 && lcm(b1/x, b0) == b1) ++ cnt;
				}
			}
		}
		std::cout << cnt << std::endl;
	}
	return 0;
}