7.Hankson 的趣味题

7.[NOIP2009 提高组] Hankson 的趣味题
难度：普及/提高-
来源：NOIP提高组

题目描述
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，请输出 00，若存在这样的 x，请输出满足条件的 x 的个数；

输入输出样例
输入#1

2
41 1 96 288
95 1 37 1776
输出#1

6
2

AC代码（C++）：

#include <bits/stdc++.h>
/*
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <ctime>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
*/
#define inf 1000000000
#define N 50000
#define ll long long
using namespace std;
int read(void)
{
    int x = 0,f = 1;char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int n,tot;
int a0,b0,a1,b1,ans;
int pri[50005];
bool mark[50005];
void getpri(void)
{
    for (int i = 2;i <= N;i++)
    {
    	if (!mark[i])
        {
            pri[++tot] = i;
        }
    	for(int j=1;j<=tot&&pri[j]*i<=N;j++)
    	{
        	mark[pri[j] * i] = 1;
        	if (pri[j] % i == 0)
            {
                break;
            }
		}
    }
}
void solve(int x)
{
    int c0 = 0,c1 = 0,c2 = 0,c3 = 0;
    while (a0 % x == 0)
    {
        a0 /= x;
        c0++;
    }
    while (a1 % x == 0)
    {
        a1 /= x;
        c1++;
    }
    while (b0 % x == 0)
    {
        b0 /= x;
        c2++;
    }
    while (b1 % x == 0)
    {
        b1 /= x;
        c3++;
    }
    if (c0 == c1 && c2 == c3)
    {
        if (c1 <= c3)
        {
            ans *= c3 - c1 + 1;
        }
        else 
        {
            ans = 0;
        }
    }
    else if (c0 != c1 && c2 != c3 && c1 != c3)
    {
        ans = 0;
    }
}
int main(void)
{
    getpri();
    n = read();
    while(n--)
    {
    	ans = 1;
    	a0 = read();
        a1 = read();
        b0 = read();
        b1 = read();
    	for (int i = 1;i <= tot;i++)
        {
            solve(pri[i]);
        }
    	if(b1 != 1)
        {
            solve(b1);
        }
    	printf("%d\n",ans);
    }
    return 0;
}

没有注释，自行学习。

by：ACGO

你的点赞和关注就是我更新题解的最大动力！
点个赞吧 ↓ ！