题目名称 405. [NOIP 2009]Hankson的趣味题
输入输出 son.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatar.Xmz 于2010-03-09加入
开放分组 全部用户
提交状态
分类标签
NOIP/CSP 数学 数论 搜索法
分享题解
通过:299, 提交:1112, 通过率:26.89%
GravatarHyoi_0Koto 100 0.000 s 0.05 MiB C++
GravatarHyoi_0Koto 100 0.000 s 0.99 MiB C++
Gravatarwire 100 0.009 s 0.51 MiB C++
GravatarTA 100 0.011 s 9.85 MiB C++
Gravatarzhengtn03 100 0.015 s 0.33 MiB C++
Gravatar_Itachi 100 0.017 s 0.10 MiB C++
Gravatarzhengtn03 100 0.018 s 0.49 MiB C++
Gravatarliu_runda 100 0.019 s 0.39 MiB C++
Gravatar_Itachi 100 0.023 s 0.10 MiB C++
Gravatar王者自由 100 0.024 s 1.72 MiB C++
本题关联比赛
20160303
至少完成十道练习
练习Noip2009
暑假综合模拟2
关于 Hankson的趣味题 的近10条评论(全部评论)
文明评论,从我做起!
Gravatar┭┮﹏┭┮
2020-10-22 20:28 27楼
文明评论,从我做起!
Gravatar海岛专业跳伞快递员
2020-10-22 19:50 26楼
常数优化:不要 memset !!!!
少开 long long ,还有压缩数组长度
Gravatar锝镆氪锂铽
2020-10-18 11:29 25楼
$i^2≤b1比i≤\sqrt{b1}$快了好多!
Gravatar夜莺
2020-04-05 17:59 24楼
我就是弱啊 质因数分解都考虑不全
GravatarRapiz
2016-10-25 08:52 23楼
删掉memset,速度提高了几十倍。。
Gravatardateri
2016-08-05 22:16 22楼
gcd a,b 不要反了QAQ 反了a,b只能拿20
Gravatar安呐一条小咸鱼。
2016-07-03 17:07 21楼
GravatarGo灬Fire
2016-07-03 15:02 20楼
好奇什么算法能比线性筛求完素数再分解质因数快,看了一下最上面的代码。。原来都是交质数表
Gravatarliu_runda
2016-06-29 10:35 19楼
板子??怎摸还有人deque,分制看起来好蛋疼
GravatarNVIDIA
2016-03-04 10:21 18楼

405. [NOIP 2009]Hankson的趣味题

★★☆   输入文件:son.in   输出文件:son.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

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

今天在课堂上,老师讲解了如何求两个正整数 $c_1$ 和 $c_2$ 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题” ,这个问题是这样的:

已知正整数 $a_0,a_1,b_0,b_1$,设某未知正整数 x 满足:

1.$x$ 和 $a_0$ 的最大公约数是 $a_1$;

2.$x$ 和 $b_0$ 的最小公倍数是 $b_1$。

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

【输入格式】

输入文件名为 son.in。第一行为一个正整数 $n$,表示有 $n$ 组输入数据。接下来的 $n$ 行每 行一组输入数据,为四个正整数 $a_0,a_1,b_0,b_1$,每两个整数之间用一个空格隔开。输入 数据保证 $a_0$ 能被 $a_1$ 整除,$b_1$ 能被 $b_0$ 整除。

【输出格式】

输出文件 son.out 共 $n$ 行。每组输入数据的输出结果占一行,为一个整数。 对于每组数据:若不存在这样的 $x$,请输出 $0$;若存在这样的 $x$,请输出满足条件的 $x$ 的个数。

【样例输入】

2 
41 1 96 288 
95 1 37 1776

【样例输入】

6 
2

【说明】

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

【数据范围】

对于 50% 的数据,保证有 $1≤a_0,a_1,b_0,b_1≤10000$ 且 $n≤100$。

对于 100% 的数据,保证有 $1≤a_0,a_1,b_0,b_1≤2,000,000,000$ 且 $n≤2000$。