- 最小公倍数和最大公约数问题
- 2017-08-24 22:38:13 @
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int x;
int y;
int num=0;
vector <int> bnum;
void qsort(int b,int e)
{
int be=bnum[(b+e)/2];
int i=b,j=e;
int temp;
while(i<=j)
{
while(bnum[i]<be)i++;
while(bnum[j]>be)j--;
if(i<=j)
{
temp=bnum[i];
bnum[i]=bnum[j];
bnum[j]=temp;
i++;
j--;
}
}
if(b<j)qsort(b,j);
if(i<e)qsort(i,e);
return;
}
int gcd(int a,int b)
{
if(b%a==0)return a;
else return gcd(b%a,a);
}
inline int lcm(int a,int b,int n)
{
return a*b/n;
}
int main()
{
cin>>x>>y;
int p=x,q=1000000;
int leng=0;
int temp=sqrt(y);
int i=2;
int j;
bnum.push_back(y);
for(i=x;i<temp;++i)
{
if(y%i==0)
{
if(i%x==0)bnum.push_back(i);
if((y/i)%x==0)bnum.push_back(y/i);
}
}
if(temp*temp==y)bnum.push_back(temp);
leng=bnum.size();
qsort(0,leng-1);
/*
cout<<endl;
for(i=0;i<leng;++i)
cout<<bnum[i]<<' ';
cout<<endl;
*/
int n,m;
for(i=0;i<leng;++i)
{
for(j=i+1;j<leng;++j)
{
n=gcd(bnum[i],bnum[j]);
m=lcm(bnum[i],bnum[j],n);
if( n==x && m==y )num++;
}
}
cout<<num*2;
return 0;
}