NOIP2010即将到来，这道题用来练练手感。
这道题的思路就是分解质因数。
首先，不难得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。
假设对于一个质因数y，a0含有a0c个y，a1含有a1c个y，b0含有b0c个y，b1含有b1c个y。
那么不难得到，如果a0c<a1c，那么就无解；如果a0c=a1c，那么x至少含有a1c个y；如果a0c>a1c，那么x只可能含有a1c个y。
同理，如果b1c<b0c，那么就无解；如果b1c=b0c，那么x至多含有b1c个y；如果b1c>b0c，那么x只可能含有b1c个y。
由此，可以求出对于每一个质数，x可能含有几个它，并求出一共有多少种选择方式。然后根据乘法原理，将每一个质数的选择方案数乘起来，就得到了答案。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-10-14
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
const int MAXSIZE=5000;
int prime_table[MAXSIZE];
int prime_table_size;
void initialize_prime_table()
{
prime_table_size=0;
prime_table[prime_table_size++]=2;
for (int i=3;prime_table_size<MAXSIZE;i++)
{
bool is_prime=true;
for (int j=0;j<prime_table_size;j++)
if (i%prime_table[j]==0)
{
is_prime=false;
break;
}
if (is_prime) prime_table[prime_table_size++]=i;
}
}
void calculate_one_step(int& a0,int& a1,int& b0,int& b1,int& result,int p)
{
int a0c=0,a1c=0,b0c=0,b1c=0;
while (a0%p==0) a0/=p,a0c++;
while (a1%p==0) a1/=p,a1c++;
while (b0%p==0) b0/=p,b0c++;
while (b1%p==0) b1/=p,b1c++;
if (a0c<a1c||b0c>b1c) result*=0;
else if (a0c==a1c&&b0c==b1c)
{
if (a1c<=b1c) result*=b1c-a1c+1;
else result*=0;
}
else if (a0c==a1c&&b0c<b1c)
{
if (a1c<=b1c) result*=1;
else result*=0;
}
else if (a0c>a1c&&b0c==b1c)
{
if (a1c<=b1c) result*=1;
else result*=0;
}
else //if (a0c>a1c&&b0c<b1c)
{
if (a1c==b1c) result*=1;
else result*=0;
}
}
int calculate(int a0,int a1,int b0,int b1)
{
//gcd(x/a1,a0/a1)=1
//gcd(b1/x,b1/b0)=1
if (a0%a1!=0||b1%b0!=0) return 0;
int result=1;
for (int i=0;i<prime_table_size;i++)
calculate_one_step(a0,a1,b0,b1,result,prime_table[i]);
if (a0!=1) calculate_one_step(a0,a1,b0,b1,result,a0);
else if (b1!=1&&b1!=a0) calculate_one_step(a0,a1,b0,b1,result,b1);
return result;
}
int main()
{
freopen(“son.in”,“r”,stdin);
freopen(“son.out”,“w”,stdout);
int n,a0,a1,b0,b1;
initialize_prime_table();
scanf(“%d”,&n);
for (int i=0;i<n;i++)
{
scanf(“%d%d%d%d”,&a0,&a1,&b0,&b1);
printf(“%d\n”,calculate(a0,a1,b0,b1));
}
return 0;
}