ZOJ 1577 GCD & LCM

这道题很水，不过WA了好多，我要崩溃，只能看仔细再交，忽然发现还有0种的可能。我的做法很简单就是枚举。设p=a*x; q=b*x;  a,b肯定互质，且a*b=y/x,当y%x!=0时肯定不可能。然后枚举互质a，b的对数乘以2就可以了。

代码：

[cpp] 
#include<iostream> 
#include<stdio.h> 
using namespace std; 
 
int GCD(int a,int b) 
{ 
    if(b==0) return a; 
    return GCD(b,a%b);  
} 
int Solve(int n) 
{ 
     int cnt=1,i; 
     for( i=2;i*i<n;i++){ 
          if( n%i!=0||n/i%i==0) continue; 
          if( GCD(n/i,i)==1) 
              cnt++; 
     } www.2cto.com
     return cnt*2; 
} 
int main() 
{ 
    int x,y; 
    while( scanf("%d%d",&x,&y)!=EOF){ 
           if(y%x!=0) printf("0/n"); 
           else if(x==y) printf("1/n"); 
           else  if(x==1) printf("2/n"); 
           else printf("%d/n",Solve(y/x));   
    } 
    return 0; 
}