题解P1029
Mr_WA
2019-05-25 09:59:55
本人是小学五年级学生,前不久刚学了最大公因数和最小公倍数,因此可以负责任地跟大家说:最大公因数最小公倍数=两数之积。用上述式子可以枚举P、Q中的一个数,另一个就用最小公倍数*最大公因数/枚举到的数。而且由上述式子可知,P和Q的积就是x1和x2的积,范围是【min(x1,x2),max(xi,x2】。基本条件(a>=maxgys)&&(a<=mingbs)&&(b>=maxgys)&&(b<=mingbs)。
但是这还不够,我们还得判断P和Q的最小公倍数和最大公因数是不是x1和x2。数学老师教了一种神奇的方法,叫更相减损术。比如要求A和B(A>=B)的最大公因数,就可以用A-B=C,B赋给A,C赋给B,知道B与C相等为止(赋值前相等)。
可用C++函数实现:
int gys(int x,int y)
{
int z=x-y;
while(y!=z)
{
if(y>x)swap(x,y);//用小减大会有BUG
x=y;
y=z;
z=x%y;
}
return y;
}//更相减损术,因为下面用了a、b,所以这里不用a,b,c,而是用x,y,z
言归正传,满足这样的条件,这组数就符合条件,he++:(a>=maxgys)&&(a<=mingbs)&&(b>=maxgys)&&(b<=mingbs)&&(gysmax==maxgys)&&(a*b/gysmax==mingbs)
上代码!
#include<iostream>
#include<cstdio>
#include<algorithm>//防止万能头出错
using namespace std;
int gys(int x,int y)
{
int z=x%y;
while(z>0)
{
x=y;
y=z;
z=x%y;
}
return y;
}//更相减损术
int maxgys,mingbs,t,he,a,b,gysmax;
int main()
{
cin>>maxgys>>mingbs;
t=maxgys*mingbs;
for(int i=1; i<=t; i++)
{
a=i;//数P
b=t/i;//数Q
gysmax=gys(a,b);
if(t%i>0)continue;
if((a>=maxgys)&&(a<=mingbs)&&(b>=maxgys)&&(b<=mingbs)&&(gysmax==maxgys)&&(a*b/gysmax==mingbs))he++;//判断条件,别忘了养成&&前后加括号的好习惯哦!
}
cout<<he;//输出
return 0;
}//华华丽丽的结束
//备注,勿抄题解!!
Tips:在判断范围时要注意,不能用<和>,应该用<=和>=,否则会漏掉P、Q正好等于x1和x2的情况!