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