洛谷P1072 Hankson的趣味题

2024-03-29 08:20:28

洛谷P1072 Hankson的趣味题

题目

题目描述
输入输出格式

输入格式
输出格式

输入输出样例

输入样例
输出样例

题解

题目

题目描述

原题
Hanks博士是 BT(Bio-Tech，生物技术)领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数 $c_1$ c1和 $c_2$ c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 $a_0,a_1,b_0,b_1$ a0,a1,b0,b1，设某未知正整数 $x$ x满足：
1. $x$ x和 $a_0$ a0的最大公约数是 $a_1$ a1；
2. $x$ x和 $b_0$ b0的最小公倍数是 $b_1$ b1。
Hankson的“逆问题”就是求出满足条件的正整数 $x$ x。但稍加思索之后，他发现这样的 $x$ x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 $x$ x的个数。请你帮助他编程求解这个问题。

输入输出格式

输入格式

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

输出格式

共 $n$ n行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的 $x$ x，请输出 $0$ 0；
若存在这样的 $x$ x，请输出满足条件的 $x$ x的个数；

输入输出样例

输入样例

2
41 1 96 288
95 1 37 1776

输出样例

6
2

题解

因为 $x$ x是 $b_1$ b1的约数，所以 $x$ x的质因子一定也是 $b_1$ b1的质因子，所以我对于 $b_1$ b1的每个质因子 $p$ p，我们可以计算 $x$ x中有多少个 $p$ p
假设 $a_0,a_1,b_0,b_1,x$ a0,a1,b0,b1,x中分别有 $m_{a_0},m_{a_1},m_{b_0},m_{b_1},m_x$ ma0,ma1,mb0,mb1,mx个质因子 $p$ p
由于 $gcd(a_0,x)=b_0$ gcd(a0,x)=b0，所以有 $3$ 3种情况：

若 $m_{a_0}>m_{b_0}$ ma0>mb0，则 $m_x=m_{b_0}$ mx=mb0
若 $m_{a_0}=m_{b_0}$ ma0=mb0，则 $m_x\geqslant m_{b_0}$ mx⩾mb0
若 $m_{a_0}<m_{b_0}$ ma0<mb0，则 $m_x$ mx无解

同理，由于 $lcm(a_1,x)=b_1$ lcm(a1,x)=b1，所以有 $3$ 3种情况：

若 $m_{a_1}<m_{b_1}$ ma1<mb1，则 $m_x=m_{b_1}$ mx=mb1
若 $m_{a_1}=m_{b_1}$ ma1=mb1，则 $m_x\leqslant m_{b_1}$ mx⩽mb1
若 $m_{a_1}>m_{b_1}$ ma1>mb1，则 $m_x$ mx无解

综合以上所有情况，我们可以得出共有 $5$ 5种情况：

若 $m_{a_0}>m_{b_0},m_{a_1}<m_{b_1},m_{b_0}=m_{b_1}$ ma0>mb0,ma1<mb1,mb0=mb1，则 $m_x=m_{b_0}=m_{b_1}$ mx=mb0=mb1
若 $m_{a_0}>m_{b_0},m_{a_1}=m_{b_1},m_{b_0}\leqslant m_{b_1}$ ma0>mb0,ma1=mb1,mb0⩽mb1，则 $m_x=m_{b_0}$ mx=mb0
若 $m_{a_0}=m_{b_0},m_{a_1}<m_{b_1},m_{b_0}\leqslant m_{b_1}$ ma0=mb0,ma1<mb1,mb0⩽mb1，则 $m_x=m_{b_1}$ mx=mb1
若 $m_{a_0}=m_{b_0},m_{a_1}=m_{b_1},m_{b_0}\leqslant m_{b_1}$ ma0=mb0,ma1=mb1,mb0⩽mb1，则 $m_{b_0}\leqslant m_x\leqslant m_{b_1}$ mb0⩽mx⩽mb1
若其他情况，则 $m_x$ mx均无解

我们将 $m_x$ mx的取法记为 $sum_p$ sump，则 $x$ x的数量为 $\prod\limits_{\text{质数}p|d}sum_p$ 质数p∣d∏sump
代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a0,a1,b0,b1,ans;
int gcd(int a,int b)
{
  return b==0?a:gcd(b,a%b);
}
long long lcm(int a,int b)
{
  return (long long)a*b/gcd(a,b);
}
int main()
{
  cin>>n;
  while(n--){
    ans=0;
    scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
    for(int i=1;i<=sqrt(b1);i++)
    if(b1%i==0){
  		if(gcd(i,a0)==a1&&lcm(i,b0)==b1) ans++;
      if(i*i!=b1) if(gcd(b1/i,a0)==a1&&lcm(b1/i,b0)==b1) ans++;;
    }
    printf("%d\n",ans);
  }
}

码农公寓