P1072hankson的趣味题

题目描述

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

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

1． $a_0a0 的最大公约数是 a1；$

2．

Hankson 的“逆问题”就是求出满足条件的正整数

输入输出格式

输入格式：

第一行为一个正整数 $能被b_0b0整除。$

输出格式：

共

对于每组数据：若不存在这样的

若存在这样的

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,n,cnt,ans;
int prime[1000000],f[1000000];
void work(int p)
{
    int na=0,nb=0,nc=0,nd=0;
    while(a%p==0){a/=p;na++;}
    while(b%p==0){b/=p;nb++;}
    while(c%p==0){c/=p;nc++;}
    while(d%p==0){d/=p;nd++;}
    if(na<nb||nc>nd||nb>nd) ans=0;
    if(na>nb&&nc<nd&&nd>nb) ans=0;
    if((na>nb||nc<nd)&&nd>=nb) ans*=1;
    if(nc==nd&&na==nb) ans*=(nd-nb+1);     
}
int main()
{
    cin>>n;
    for(int i=2;i<=45000;i++){if(!f[i])prime[++cnt]=i;for(int j=1;j*i<=45000;j++)f[j*i]=1;}
    for(int k=1;k<=n;k++)
    {
        ans=1;
        cin>>a>>b>>c>>d;
        for(int i=1;i<=cnt&&ans;i++)if(d%prime[i]==0)work(prime[i]);
        if(d>1)work(d);
        cout<<ans<<endl;
    }
}

P1072hankson的趣味题

题目描述

输入输出格式

相关推荐