总时间限制: 

1000ms

内存限制: 

65536kB

描述

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

条件:

1.P,q是正整数

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

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

 

输入

一行，包含两个正整数x0和y0，中间用单个空格隔开。

输出

一个整数，即满足条件的个数。

样例输入

3 60

样例输出

4

提示

此时的P q分别为:

3 60

15 12

12 15

60 3

所以:满足条件的所有可能的两个正整数的个数共4种。

来源

NOIP2001复赛 普及组 第二题

　　　若num1，与num2的最大公约数为gcd(num1,num2)，最小公倍数lcm(num1,num2);则有lcm(num1,num2)*gcd(num1,num2)==num1*mum2。

因为lcm(a,b)==(a*b)/gcd(a,b),所以：

1 #include
     
       2 using namespace std; 3 inline int exgcd(int a,int b,int &x,int &y){ 4     if(b==0){ 5         x=1,y=0; 6         return a; 7     } 8     else{ 9         int ans=exgcd(b,a%b,y,x);10         y-=x*(a/b);11         return ans;12     }13 }14 15 int N,M,x,y;16 int cheng;17 int maxx;18 int ANS;19 int main(){20     scanf("%d%d",&N,&M);21     cheng=N*M;22     maxx=int(sqrt(double(cheng)));23     for(int i=1;i<=maxx;i++){24         if(cheng%i==0){25             int tmp1=i; int tmp2=cheng/i;26             if(exgcd(tmp1,tmp2,x,y)==N){27                 ANS+=2;28             }29         }30     }31     cout<