能力值：
( LV12，RANK：570 )
|
-
-
2 楼
//差一点就全部通过的解答，下次来解释了，基于code：：blocks跟它自己带的编译器调试通过
#include <iostream>
using namespace std;
int main()
{
//cout << "Hello world!" << endl;
int x0,y0;
cin>>x0>>y0;
int temp=y0/x0;
int i,j=0;
for (i=2;i<=temp;i++)
{
if (temp %i==0) j++;
while (temp % i==0)
{
temp=temp /i;
}
}
temp=1;
for (i=1;i<=j;i++) temp=temp*2;
cout<<temp;
return 0;
}
//比较变态的一组数据是x0=12，y0=4096.根本不可能出现的情况。x0不能整除y0.
|
能力值：
![]()
(RANK：1060 )
|
-
-
3 楼
代码缩进太牛了。
P=gcd(P,Q)*p
Q=gcd(P,Q)*q
gcd(p,q)=1
lcm(P,Q)=lcm(p,q)*gcd(P,Q)
lcm(p,q)=lcm(P,Q)/gcd(P,Q)
gcd(p,q)=1
lcm(p,q)=pq=lcm(P,Q)/gcd(P,Q)
就算试除也不应该除到y0/x0
|
能力值：
![]()
(RANK：570 )
|
-
-
4 楼
数学都忘得差不多了。当然也没认真学，楼主这样枚举效率太低了吧
|
能力值：
( LV12，RANK：570 )
|
-
-
5 楼
过了午夜假期套餐就结束了。还没有去大学，唉……乘着还有两个小时，粗糙的写一下原理，见谅。
易知p*q=x0*y0【1】
（p/x0,q/x0)=1【2】
(p/x0)*(q/x0)=y0/x0【3】
由于已经知道y0与x0，可以求得y0/x0
所以现在我们只要求出符合条件【2】的p/x0和q/x0好了。
记y0/x0为temp。我们对temp进行因式分解。
假设temp=20，那么它的素因子集合就是{2，5},记为集合A。|A|=2，2的2次等于4.
解释：虽然20=2×2×5，但是如果2是p的因子就一定不是q的因子，否则不符合【2】，所以我们不必完全对它因式分解（还有一点是因为题目没有让你求p，q）。只要知道它的不同的素因子有几个就行了。因为x0是它的最大公约数，所以A中的元素不可能同为p和q的因子。题目相当于求|A的幂集合|。
我的解答的效率不高，在求a的幂集合的元素个数时随手写了一个可用的。感觉代码量比较少。最容易的改进当然就是循环2个2个的跳。
汗，现在突然发现 for (i=2;i<=temp;i++)temp少了个根号。我晕……太久没有写代码了。相信加个根号大家开始编程的时候都学过的是吧？
|
|
|
|
