首页 > 其他分享 >P1072 [NOIP2009 提高组] Hankson 的趣味题【GCD】

P1072 [NOIP2009 提高组] Hankson 的趣味题【GCD】

时间:2024-06-22 19:02:19浏览次数:21  
标签:GCD int NOIP2009 a1 a0 b0 b1 P1072 Hankson

[NOIP2009 提高组] Hankson 的趣味题

题目描述

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

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

  1. x x x 和 a 0 a_0 a0​ 的最大公约数是 a 1 a_1 a1​;

  2. x x x 和 b 0 b_0 b0​ 的最小公倍数是 b 1 b_1 b1​。

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

输入格式

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

输出格式

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

对于每组数据:若不存在这样的 x x x,请输出 0 0 0,若存在这样的 x x x,请输出满足条件的 x x x 的个数;

样例 #1

样例输入 #1

2 
41 1 96 288 
95 1 37 1776

样例输出 #1

6 
2

提示

【样例解释】

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

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

【数据范围】

  • 对于 50 % 50\% 50% 的数据,保证有 1 ≤ a 0 , a 1 , b 0 , b 1 ≤ 10000 1\leq a_0,a_1,b_0,b_1 \leq 10000 1≤a0​,a1​,b0​,b1​≤10000 且 n ≤ 100 n \leq 100 n≤100。
  • 对于 100 % 100\% 100% 的数据,保证有 1 ≤ a 0 , a 1 , b 0 , b 1 ≤ 2 × 1 0 9 1 \leq a_0,a_1,b_0,b_1 \leq 2 \times 10^9 1≤a0​,a1​,b0​,b1​≤2×109 且 n ≤ 2000 n≤2000 n≤2000。

NOIP 2009 提高组 第二题

问题链接: P1072 [NOIP2009 提高组] Hankson 的趣味题
问题分析: 最大公约数问题,不解释。
参考链接: (略)
题记: (略)

AC的C++语言程序如下:

/* P1072 [NOIP2009 提高组] Hankson 的趣味题 */

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while (n--) {
        int a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;
        int p = a0 / a1, q = b1 / b0, cnt = 0;
        for (int i = 1; i * i <= b1; i++)
            if (b1 % i == 0) {
                if (i % a1 == 0 && __gcd(i / a1, p) == 1 && __gcd(q, b1 / i) == 1)
                    cnt++;
                int j = b1 / i;
                if (j == i) continue;
                if(j % a1 == 0 && __gcd(j / a1, p) == 1 && __gcd(q, b1 / j) == 1)
                    cnt++;
            }
        cout << cnt << endl;
    }
    return 0;
}

标签:GCD,int,NOIP2009,a1,a0,b0,b1,P1072,Hankson
From: https://blog.csdn.net/tigerisland45/article/details/139886611

相关文章

  • 使用 GCD 实现属性的多读单写
    使用GrandCentralDispatch(GCD)实现多读单写的属性首先需要确保在多线程环境下的线程安全性。可以使用GCD提供的读写锁机制dispatch_rwlock_t或者dispatch_queue_t来实现这个功能。Swift版本的实现怎样创建一个并发队列?//使用Swift来实现的首个好处就是:......
  • [GDOI2014] 世界杯&[AHOI2001] 彩票摇奖&[NOIP2009 普及组] 分数线划定
    [GDOI2014]世界杯de题目描述(复制的题目可能有错,请用你手头上的)3014年世界杯足球赛就要开始了!作为卫冕冠军中国足球队的教练,手下每位球员都是猛将,如何摆出最强的11人阵容也是一件幸福的烦恼事啊。众所周知,足球阵容里的11个球员都会被分配到场上某一个特别的位置,而这......
  • 两个 GCD 经典问题
    相当Trivial的一篇东西。[ABC177E]Coprime给定\(n\)个数\(a_{1\simn}\),值域为\(V\)。求:是否全部互质是否两两互质问题1:是否全部互质即求\(\gcd\limits_{i=1}^na_i\)是否为\(1\)。直接\(1\simn\)辗转相除求\(\gcd\)。时间复杂度\(O(n+\logV)\)。(......
  • 最大公约数(gcd())和最小公倍数(lcm())的c语言和c++详细解法
    最大公约数(gcd())和最小公倍数(lcm())最大公约数:定义:两个或多个整数共有的约数中最大的一个。例如:整数12和18,他们的公约数有1、2、3、6,其中最大的公约数是6。c语言解法:辗转相除法和更相减损法1、辗转相除法:思路:先求解较大的数除以较小的数的余数,再用较小的数除以前......
  • CF1458A Row GCD
    题目链接:https://codeforces.com/problemset/problem/1458/A这道题比较考察对辗转相除法的理解.对于gcd的题目,gcd(a,b)=gcd(a,b-a)是一个很常见的trick,知道这个性质即可秒杀本题.gcd也可以像前缀和那样来维护还需要注意一个细节,由于a[i]-a[i-1]有可能出现负数,所以要先排序......
  • GCD-sequence(Round 950)
    #include<bits/stdc++.h>#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("in.txt","rt",stdin);freopen......
  • [NOIP2009 普及组] 多项式输出
    题目描述一元 ......
  • GCD构造排列
    题目给定一个长度为n的数组\(a\),试复原长度为n的排列\(p\)其中\(a_i=gcd(p_1,p_2,...,p_i)\),也就是说,\(a_i\)表示排列\(p\)中前\(i\)个数字的最大公约数。(由于数组\(a\)可能是错误的,故有可能无解,此时输出\(-1\)即可)https://ac.nowcoder.com/acm/problem/269091Input输......
  • exgcd 通解(新)
    可能不全,老文章在这什么是通解,我们知道二元一次方程,是如果只有一个式子,那么解会有无数个,而通解就是指让我们只找到一个解就可以推出其他所有解的式子。注意以下变量都为整数。知道了定义下面就是推式子了,首先设\(x,y\)是\(ax+by=\gcd(a,b)\)的一个解,那么有\[y=\le......
  • CSP历年复赛题-P1067 [NOIP2009 普及组] 多项式输出
    原题链接:https://www.luogu.com.cn/problem/P1067题意解读:模拟法依次输出多项式内容即可,但是需要考虑的周全,主要有以下关键点:1、系数为0时不输出多项式2、第一个符号,只有负号才输出3、次数不为0时,不输出为1的系数;次数为0时,输出所有系数4、次数为1时,不输出次数;次数为0时不输......