C语言之最大公约数和最小公倍数问题

题目描述

输入两个正整数 x0​,y0​，求出满足下列条件的 P,Q 的个数：

1. P,Q 是正整数。

2. 要求 P,Q 以 x0​ 为最大公约数，以 y0​ 为最小公倍数。

试求：满足条件的所有可能的 P,Q 的个数。

输入格式

一行两个正整数 x0​,y0​。

输出格式

一行一个数，表示求出满足条件的 P,Q 的个数。

输入

3 60

输出

4

说明/提示

P,Q 有 4 种：

1. 3,60。
2. 15,12。
3. 12,15。
4. 60,3。

对于 100% 的数据，2≤x0​,y0​≤10^5。

#include<stdio.h> int gcd(int a,int b)//判断最小公倍数 { while(b!=0){ int t=a%b; a=b; b=t; } return a;//a即为最小公倍数 } int main() { int x,y; scanf("%d%d",&x,&y); if(y%x!=0){//最小公倍数一定是最大公约数的倍数，如果不是，则没有解，直接打印出0退出。 printf("0\n"); return 0; } int n=y/x;//最小公倍数的作用只是和最大公因数找出p的范围。 int count=0; int p; for(p=1;p*p<=n;p++){ if(n%p==0){//虽然我们明确n=p*q,但是并不能确定1~sqrt(n)内的数除以p等于q. int q=n/p;//到这一步只是求得了p和q两个因子，但二者不一定是互质的，所以后面还要判断是否互质。只有是互质的才能得出x是最大公因数。 if((gcd(p,q))==1){//判断p和q是否互质 if(p==q){ count++;//说明在计算a和b这两个数的时候得到的a和b是相等的，只有一个结果，所以只需要加1. }else{ count+=2;//说明得到的a和b是不相等的， } } } } printf("%d\n",count); return 0; }

详细解析上述代码逻辑：数学逻辑挺强

1.n=y/x;最大公约数是x，最小公倍数是y，设这两个数为a,b,p和q为去掉最大公约数后，各自独有的部分。而a=x*p,b=x*q.其中p和q是互质的正整数，即二者除了1没有其他公因数。因为p和q还有大于1的公因数，则x就不是最大公约数了。

解析上述：假设有a=12,b=18,他们的最大公约数是6，即x=6。可以写成12=6*2,18=6*3,即a=12=x*p(2),b=18=x*q(3).一般化即为：a=x*p,b=x*q。

为什么p和q必须互质：如果a=40=10*4,b=60=10*6,则p和q不互质，则10不是二者的最大公约数，二者的最大公约数其实是20.所以如果p和q不互质，则x并不是最大公因数。

2.为什么要定义n=y/x：a*b=(x*p)*(x*q)=x^2*p*q,所以a*b/x=x*p*q,即最小公倍数y=a*b/x=x*p*q,所以y/x=p*q.所以令n=y/x,则n=p*q.

定义n=y/x，是因为n通常比y小很多，只需要对n进行因数分解，并检查每对因数是否互质，避免了直接枚举a和b大量结合。

3.实例演示：

假设x=3,y=60.计算n=y/x=60/3=20;

找到所有互质的整数对（p,q)使得p*q=20。20的因数对(1, 20)、(2, 10)、(4, 5)、(5, 4)、(10, 2)、(20, 1)。 其中互质的对是：(1, 20) 和 (4, 5)（注意 (5, 4) 与 (4, 5) 视为同一对的不同顺序，但通常只计算一次，因为 a 和 b 的顺序不影响数对）。对应的 (a, b) 为：(3*1, 3*20) = (3, 60)。(3*4, 3*5) = (12, 15)所以有两组解。(由题意得x=3,p和q互质只有p=1,q=20,所以a=x*p,b=x*q)（这是通过p和q计算的a和b两个数）

4.为什么循环是p*p<=n:我们要通过循环找到所有的（p,q)整数对，使得p*q=n；p和q互质。

为什么用 p * p <= n 而不是 p <= n？

思想实验：

假设 n = 100：

· 如果 p = 1，那么 q = 100/1 = 100
· 如果 p = 2，那么 q = 100/2 = 50
· 如果 p = 4，那么 q = 100/4 = 25
· 如果 p = 5，那么 q = 100/5 = 20
· 如果 p = 10，那么 q = 100/10 = 10
· 如果 p = 20，那么 q = 100/20 = 5

由上述可得，当p>sqrt(n)时，相当于p和q又发生交换。我们要得到的p和q其实是p<=sqrt(n)时的值。这样可以减少遍历，因为二者一样的，只需要计数加2即可。

通过上述方法求出来的p和q并不是满足条件的两个数，而是因子，通过这两个因子求得的a和b才是最终的满足条件的两个数，即为下面的：

1. 3,60。
2. 15,12。
3. 12,15。
4. 60,3。