gf_boyin 发表于 2023-11-30 23:11 回复楼主 #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++代码