题目描述 Description

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:  1.P,Q是正整数

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

试求:满足条件的所有可能的两个正整数的个数.

输入描述 Input Description

二个正整数x0,y0

输出描述 Output Description

满足条件的所有可能的两个正整数的个数

样例输入 Sample Input

3 60

样例输出 Sample Output

4

WIKIOI难度等级：通过初赛

总耗时：346ms  内存占用：0kb  语言：C++  代码：1042B

1. #include <iostream> 
2.   
3. using namespace std; 
4.   
5. int gcd(int a,int b) 
6. { 
7.     if(a<b) 
8.     { 
9.         return gcd(b,a); 
10.     } 
11.     if(b==0) 
12.     { 
13.         return a; 
14.     } 
15.     if(a&1) 
16.     { 
17.         if(b&1) 
18.         { 
19.             return gcd(b,a-b); 
20.         } 
21.         else 
22.         return gcd(a,b>>1); 
23.     } 
24.     else 
25.     { 
26.         if(b&1) 
27.         { 
28.             return gcd(a>>1,b); 
29.         } 
30.         else 
31.         { 
32.             return gcd(a>>1,b>>1)<<1; 
33.         } 
34.     } 
35. } 
36.   
37. int main(int argc,char *argv[]) 
38. { 
39.       
40.     int x0,y0,i,j,sign=0,temp; 
41.       
42.     cin>>x0>>y0; 
43.     for(i=x0;i<=y0;i++) 
44.     { 
45.         for(j=x0;j<=y0;j++) 
46.         { 
47.             if(j%x0==0&&i%x0==0) 
48.             { 
49.                 temp=gcd(i,j); 
50.                 if(temp==x0) 
51.                 { 
52.                     if(i*j/x0==y0) 
53.                     { 
54.                         sign++; 
55.                     } 
56.                 } 
57.             } 
58.         } 
59.   
60.     } 
61.     cout<<sign; 
62.       
63.     return 0; 
64. }