注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

NOIP2009[Hankson的趣味题/son]  

2010-10-14 13:40:39|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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;

}

 

  评论这张
 
阅读(3956)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018