#C. GCD和LCM是好朋友(数据加强版) 传统题 1000ms 125MiB 背景
- 最大公约数 ( � � � � � � � � � � � � � � � � � � � � � ( � � � ) ) (GreatestCommonDivisor(GCD)) 1.1 基本概念 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为 （ � ， � ） （a，b），同样的， � ， � ， � a，b，c的最大公约数记为 （ � ， � ， � ） （a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数， � ， � a，b的最小公倍数记为[ � ， � a，b]。
1.2 算法 短除法
求 � ， � p，q的最大公约数：
image
当 � , � a,b为互质数时候， � x为最大公约数， �
� × � × � y=x×a×b为最小公倍数
辗转相除法
辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。
用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。
image
- 最小公倍数 ( � � � � � � � � � � � � � � � � � � � ( � � � ) ) (LeastCommonMultiple(LCM)) 2.1 基本概念 两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为[ � ， � a，b]，同样的， � ， � ， � a，b，c的最小公倍数记为[ � ， � ， � a，b，c]，多个整数的最小公倍数也有同样的记号。
与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（ � ， � a，b）。关于最小公倍数与最大公约数，我们有这样的定理：( � , � a,b)[ � , � a,b]= � × � a×b( � , � a,b均为整数)
2.2 算法 公式法
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即 （ � ， � ） × [ � ， � ]
� × � （a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
题目说明 输入二个正整数x，y，求出满足下列条件的P，Q的对数。
条件：
P，A是正整数； 要求P，Q以x为最大公约数，以y为最小公倍数。 试求：
满足上述条件的所有可能的两个正整数的P,Q的对数。
输入格式 每个测试文件只包含一组测试数据，每组两个正整数x和y。
输出格式 对于每组输入数据，输出满足条件的所有可能的两个正整数的对数的方案总数。
样例 输入数据 1 3 60 输出数据 1 4 下面是对样例数据的说明：
输入3 60
此时的 � , � P,Q分别为:
序号 � P � Q 1 1 3 3 60 60 2 2 15 15 12 12 3 3 12 12 15 15 4 4 60 60 3 3 所以上述有4种可能，输出答案4
数据范围： 测试点 � x 范围 � y 范围 1 1~ 3 3 � < 20 x<20 � < 5000 y<5000 4 4~ 7 7 � < 1 0 2 x<10 2
� < 1 0 8 y<10 8
8 8~ 10 10 � < 1 0 14 y<10 14 有没有大佬给我的代码更改一下求求了c++ 我的代码如下：
#include <iostream>
using namespace std;
// 辗转相除法求最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// 求满足条件的对数方案总数
int countPairs(int x, int y) {
int count = 0;
int max_gcd = gcd(x, y);
for (int i = 1; i <= max_gcd; i++) {
for(int j=1;j<=max_gcd;j++)
if (max_gcd % i == 0 && x * y % (i * i) == 0) {
count++;
}
}
return count;
}
int main() {
int x, y;
cin >> x >> y;
int result = countPairs(x, y);
cout << result << endl;
return 0;
}