200. Hankson的趣味题

绝地灬酷狼 2021-10-29 14:38 188阅读 0赞

题目链接：https://www.acwing.com/problem/content/202/

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

整除。  
输出格式

输出共n行。

每组输入数据的输出结果占一行，为一个整数。

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

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

1≤n≤2000  
,  
1≤a0,a1,b0,b1≤2∗109

输入样例：

2  
41 1 96 288  
95 1 37 1776

输出样例：

6  
2

分析：  
x是d的约数。所以x的质因子就是d的质因子。那么，我们枚举d的质因子p，通过a，b,c,和d的质因子p的个数来推测x能有多少个p。通过不断枚举即可。

#include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int n,top;
    ll a,b,c,d,ans;
    ll prime[101001];
    int id[10000010];
    
    void init()
    {
        ll n = sqrt(2e9);
        for(int i = 2; i <= n; i ++)
        {
            if(id[i] == 0)
            {
                prime[++ top] = i;
                id[i] = i;
            }
            for(int j = 1; j <= top; j ++)
                if(prime[j] > id[i] || prime[j] > n / i)
                    break;
                else
                    id[i * prime[j]] = prime[j];
        }
    }
    
    ll get(ll &a,ll &p)
    {
        ll cnt = 0;
        while(a % p == 0)
        {
            a = a / p;
            ++ cnt;
        }
        return cnt;
    }
    
    ll solve(ll p)
    {
        if(p > d) return 0;
        ll ma = get(a,p);
        ll mb = get(b,p);
        ll mc = get(c,p);
        ll md = get(d,p);
        ll x = 1;
       // printf("ma = %lld mb = %lld mc = %lld md = %lld\n",ma,mb,mc,md);
        if(ma == mc && mb == md && mc <= md) x = md - mc + 1;
        else if(ma == mc && mb < md && mc <= md) x = 1;
        else if(ma > mc && mb < md && mc == md) x = 1;
        else if(ma > mc && mb == md && mc <= md) x= 1;
        else  x = 0;
        ans *= x;
        return 1;
    }
    
    int main()
    {
        init();
        scanf("%d",&n);
        while(n --)
        {
            ans = 1;
            scanf("%lld%lld%lld%lld",&a,&c,&b,&d);
            for(int i = 1; i <= top; i ++)
            {
               // printf("prime = %lld\n",prime[i]);
                ///if(d == 1) break;
                if(d % prime[i]) continue;
                if(solve(prime[i]) == 0) break;
            }
            if(d != 1)
                solve(d);
            printf("%lld\n",ans);
        }
    }