NOIP2009[Hankson的趣味题/son]

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;


}


 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注