| 题目名称 | 536. 双亲数 |
|---|---|
| 输入输出 | parents.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 10 |
| 题目来源 |
 常庆卫
于2011-04-12加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：68， 提交：122， 通过率：55.74% | ||||
|
黄笑凡 |
100 | 0.048 s | 14.60 MiB | C++ |
|
李佩轩 |
100 | 0.051 s | 5.82 MiB | C++ |
|
fyl |
100 | 0.052 s | 8.90 MiB | C++ |
|
许子康 |
100 | 0.055 s | 12.71 MiB | C++ |
|
AntiLeaf |
100 | 0.074 s | 8.87 MiB | C++ |
|
石文慧 |
100 | 0.075 s | 16.79 MiB | C++ |
|
徐文博 |
100 | 0.099 s | 7.92 MiB | C++ |
|
sxysxy |
100 | 0.102 s | 8.87 MiB | C++ |
|
ZLJ |
100 | 0.103 s | 11.76 MiB | C++ |
|
梁永硕 |
100 | 0.115 s | 8.89 MiB | C++ |
| 本题关联比赛 | |||
| 20110412 | |||
| 20110412 | |||
| 关于 双亲数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
连跪两次居然是数组没开到$10^6$……
夜莺
2020-03-31 12:31
7楼
| ||||
|
没开LL连输出都没了
AAAAAAAAAA
2017-09-09 20:17
6楼
| ||||
|
同cogs469[NOI2010]能量采集
| ||||
|
莫比乌斯反演吼啊，QnQ两次WA在long long上了，连输入的a, b, d也应该都用long long才对。
| ||||
|
本人太弱 只能把莫比乌斯学了。。。。
| ||||
|
莫比乌斯反演，记得开long long
| ||||
【问题描述】
小 D 是一名数学爱好者，他对数字的着迷到了疯狂的程度。
我们以 d = gcd(a, b) 表示 a 、 b 的最大公约数，小 D 执著的认为，这样亲密的关系足可以用双亲来描述，此时，我们称 有序 数对 (a, b) 为 d 的双亲数。
与正常双亲不太相同的是，对于同一个 d ，他的双亲太多了 >_<
比如， (4, 6), (6, 4), (2, 100) 都是 2 的双亲数。
于是一个这样的问题摆在眼前，对于 0 < a <= A, 0 < b <= B ，有多少 有序 数对 (a, b) 是 d 的双亲数？
【输入文件】
输入文件只有一行，三个正整数 A 、 B 、 d (d <= A, B) ，意义如题所示。
【输出文件】
输出一行一个整数，给出满足条件的双亲数的个数。
【数据约定】
对于 40% 的数据满足 0 < A, B < 10^4
对于 100% 的数据满足 0 < A, B < 10^6
【样例】
输入样例
5 5 2
输出样例
3
【样例解释】
满足条件的三对双亲数为 (2, 2) (2, 4) (4, 2)