题目描述：输入两个正整数 x0,y0，求出满足下列条件的 P,Q 的个数：P,Q 是正整数。要求 P, Q以 x0 为最大公约数，以 y0 为最小公倍数。试求：满足条件的所有可能的 P,Q 的个数。
输入格式：一行两个正整数 x0,y0。
输出格式：一行一个数，表示求出满足条件的 P,Q 的个数。
首先，介绍一个定理：两个整数的最小公倍数和最大公约数的乘积等于这两个整数的乘积。即：
ab=(a,b)[a,b].
根据它，我们可以枚举i，j，判断其是否满足条件。先算出gcd(i,j),这里的gcd即最大公约数。使用辗转相除法：
int gcd(int a,int b){return (a%b==0)?b:gcd(b,a%b);}
这里使用了三目运算符，即当问号前的表达式为true时返回冒号前的值，反之返回冒号后的值。
于是，问题自然来了：i和j的枚举范围是多少？总不能让它一直枚举下去吧！
根据最大公约数和最小公倍数的定义，i和j一定在[p,q]范围内，也就是在最大公约数和最小公倍数之间（包括两者自身）。
并且，根据上面的定理，知道了两个数和其最大公约数，就能算出最小公倍数，完全不用再专门写一个计算最小公倍数的函数。
第一版代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int gcd(int a,int b){return (a%b==0)?b:gcd(b,a%b);} int p,q,ans; int main() { cin>>p>>q; for(int i=p;i<=q;i++) { for(int j=p;j<=q;j++) { if(gcd(i,j)==p&&i*j/gcd(i,j)==q)//算出最小公倍数 { //cout<<i<<" "<<j<<endl;（调试用） ans++; } } } cout<<ans; }
没错，根据我以往写博客的风格，第一版代码肯定是错的。结果是，有4个点TLE。
超时说明代码大体思路绝对没错，但是有很大的优化空间。
我不知道哪来的自信，认为这只是由于爆int了而已。然而把int修改为long long以后，结果和上次一样。
我突然想到，j从p（最大公约数）开始累加，每次加的都是1。其实完全不用，可以改成每次加p。这样仍然能保证p是j的约数，但时间复杂度减小了！p越大，时间复杂度减少的越多！
第二版代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int gcd(int a,int b){return (a%b==0)?b:gcd(b,a%b);} int p,q,ans; int main() { cin>>p>>q; for(int i=p;i<=q;i++) { for(int j=p;j<=q;j+=p) { if(gcd(i,j)==p&&i*j/gcd(i,j)==q)//唯一的改变 { //cout<<i<<" "<<j<<endl; ans++; } } } cout<<ans; }
结果，还是有两个点TLE。我又考虑了一下。能不能从第一层循环改变一些东西呢？
顺承第二版代码的思路，加一个判断，判断i是否是p的倍数以及q的因数，不行就跳过这次循环！
第三版代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int gcd(int a,int b){return (a%b==0)?b:gcd(b,a%b);} int p,q,ans; int main() { cin>>p>>q; for(int i=p;i<=q;i++) { if(i%p!=0||q%i!=0) continue;//加入判断 for(int j=p;j<=q;j+=p) { if(gcd(i,j)==p&&i*j/gcd(i,j)==q) { //cout<<i<<" "<<j<<endl; ans++; } } } cout<<ans; }
终于AC了。我计算了一下，时间差距还是很大的。第一版代码当p=12,q=4096时，运行时间为1.5秒左右，第二版代码就减少到了零点几秒，第三版代码的就可以忽略不计了。当然，如果数据再大，第三版代码就可能也应付不了。甚至可能有题会引入高精度计算最大公约数或最小公倍数。
改进代码，是每个程序员的自我修养！