P1072 Hankson 的趣味题

题目描述

Hanks 博士是 BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足：

1． x 和 a0 的最大公约数是 a1；

2． x 和 b0 的最小公倍数是 b1。

Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。

输入输出格式

输入格式：

第一行为一个正整数 n，表示有 n 组输入数据。接下来的 n 行每行一组输入数据，为四个正整数 a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除，b1 能被 b0 整除。

输出格式：

输出文件 son.out 共 n 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 x，请输出 0；

若存在这样的 x，请输出满足条件的 x 的个数；

输入输出样例

输入样例#1：

2

41 1 96 288

95 1 37 1776

输出样例#1：

6

2

说明

【说明】

第一组输入数据，x 可以是 9、18、36、72、144、288，共有 6 个。

第二组输入数据，x 可以是 48、1776，共有 2 个。

【数据范围】

对于 50%的数据，保证有 1≤a0，a1，b0，b1≤10000 且 n≤100。

对于 100%的数据，保证有 1≤a0，a1，b0，b1≤2,000,000,000 且 n≤2000。

NOIP 2009 提高组第二题

/*

    通过看说明，发现所有x好像满足两个条件

    1.x<=b1

    2.他们是等比数列

    所以我就暴力枚举出第一项和第二项，找出公比，进行计数

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,a0,a1,b0,b1;

bool check(int x){

    if((__gcd(x,a0)==a1)&&((x*b0)/__gcd(x,b0)==b1))return ;

    return ;

}

int main(){

    scanf("%d",&n);

    while(n--){

        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);

        long long x1=,x2=;

        for(int i=;i<=b1;i++){

            if(check(i)){

                if(!x1)x1=i;

                else {x2=i;break;}

            }

        }

        if(!x1){puts("");continue;}

        if(!x2){puts("");continue;}

        int cnt=;

        int bi=x2/x1;

        while(){

            long long now=x2*bi;

            if(now>b1)break;

            cnt=cnt+;

            x2=now;

        }

        printf("%d\n",cnt);

    }

}

20分乱搞

/*

    分解质因数

    稍微懂点数论的人便知道，x最多只会有一个大于根号x的质因子

    观察数据：根号2000000000在45000左右

    打表发现，50000以内的质数只有5133个！ 质数非常少！

    先预处理出50000以内的所有质数

    然后我们就可以愉快地枚举所有质数，质因数分解a0,b0,a1,b1。

    因为 GCD是取质数的幂的最小值，LCM是取质数的幂的最大值。

    所以我们可以对于每个质数得出一个可取数量的区间，乘起来就是答案了。

    最后再特判一个大于50000的质数即可。

    时间复杂度O（5000n）

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#ifdef WIN32

#define PLL "%I64d"

#else

#define PLL "%lld"

#endif

using namespace std;

int n,a0,a1,b0,b1,p[],cnt;

bool vis[];

void prepare(){

    for(int i=;i<=;i++){

        if(!vis[i])p[++cnt]=i;

        for(int j=;j<=cnt&&i*p[j]<=;j++){

            vis[i*p[j]]=;

            if(i%p[j]==)break;

        }

    }

}

int main(){

    freopen("Cola.txt","r",stdin);

    prepare();

    scanf("%d",&n);

    while(n--){

        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);

        if(a1>a0||b1<b0){puts("");continue;}

        int la,lb,ra,rb,l,r;

        int aa0=,aa1=,bb0=,bb1=;

        long long ans=;

        for(int i=;i<=cnt;i++){

            if(a0==&&a1==&&b0==&&b1==)break;

            la=lb=l=,ra=rb=r=;aa0=aa1=bb0=bb1=;

            while(a0%p[i]==){a0/=p[i];aa0++;}

            while(a1%p[i]==){a1/=p[i];aa1++;}

            while(b0%p[i]==){b0/=p[i];bb0++;}

            while(b1%p[i]==){b1/=p[i];bb1++;}

            if(aa1>aa0||bb1<bb0){ans=;break;}

            la=aa1; rb=bb1;

            if(aa0>aa1) ra=aa1;

            if(bb0<bb1) lb=bb1;

            l=max(la,lb);r=min(ra,rb);

            if(r<l){ans=;break;}

            ans=1LL*ans*(r-l+);

        }

        if(ans==){puts("");continue;}

        if(!(a0==&&a1==&&b0==&&b1==)){

            if(a1>a0||b1<b0){puts("");continue;}

            if(a1==a0&&a1!=)ans<<=;

            if(b0==b1&&b1!=)ans<<=;

        }

        printf(PLL"\n",ans);

    }

}

100分数论

巴特西

洛谷P1072 Hankson 的趣味题

P1072 Hankson 的趣味题

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章