# NOIP2009[Hankson的趣味题/son]

NOIP2010即将到来，这道题用来练练手感。

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;

}