题解【P1029】最新版

本人是小学五年级学生，前不久刚学了最大公因数和最小公倍数，因此可以负责任地跟大家说：最大公因数最小公倍数=两数之积。用上述式子可以枚举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++函数实现： ```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) 上代码！ ```c 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=maxgysmingbs; 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)&&(ab/gysmax==mingbs))he++;//判断条件，别忘了养成&&前后加括号的好习惯哦！ } cout<<he;//输出 return 0; }//备注，勿抄题解！！ ``` Tips：在判断范围时要注意，不能用<和>，应该用<=和>=，否则会漏掉P、Q正好等于x1和x2的情况！ 如有不足之处，请dalao们指出！