这是一个创建于 1730 天前的主题，其中的信息可能已经有所发展或是发生改变。
定义: d(n) 为 n 的所有除数之和(不包括 n 自身，最小为 1 )，例如:
-
220 的除数是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 所以
d(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 -
284 的除数是 1, 2, 4, 71, 142 所以
d(284) = 1 + 2 + 4 + 71 + 142 = 220
定义: 因为 d(220) = 284, d(284) = 220 所以 220 和 284 这两个数都被称为 友好数
Question 在小于一亿的数中，共有多少个友好数
- 我计算的答案是 467
- 昨天的题，欢迎继续讨论
第 1 条附言 · 2020-03-23 16:24:56 +08:00
值得一提的是 如果 d(a) = b 并且 d(b) = a, 当 a ≠ b 当时候才能称 a 和 b 为 友好数
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
 |
1
Xusually 2020-03-23 16:17:18 +08:00
1 万以内 10 个
10 万以内 24 个 100 万还在算，随手写了个伪代码，好慢。 另外，自身的友好数是自身的，也计算在内的吧，我没有排除。比如目前看到的：28 、8128 。 |
 |
2
YUX OP @Xusually #1 谢谢提醒 我忘记加上这个限制了。d(a) = b 并且 d(b) = a 并且 a ≠ b 才能称 a 和 b 为 *友好数*
> If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers. |
 |
3
luckyrayyy 2020-03-23 16:34:44 +08:00
@Xusually 你这 10 个是排除了的吧？不排除我看是 14 个啊
|
|
4
YUX OP 分享一些结果：
10000 -> 10 100000 -> 26 1000000 -> 82 |
|
5
Xusually 2020-03-23 16:46:46 +08:00
@luckyrayyy 嗯，代码有点问题，停了重新来。本来想写个流程示例代码的，结果随手写完就跑起来了。毫无优化，速度感人。
|
|
6
YUX OP |
 |
8
AAASUKA 2020-03-23 17:02:03 +08:00
用一个 1 亿长的数组，序号代表数字 n，值存放 d(n)怎么样？
|
 |
9
input2output 2020-03-23 17:16:56 +08:00
第一反应先算素数，试着算了一下，结果到 1e6 就开始吃力了
|
 |
10
silentx 2020-03-23 17:23:21 +08:00
一下是 1000w 的 感觉不优化 1y 速度感人了
220 - 284 284 - 220 1184 - 1210 1210 - 1184 2620 - 2924 2924 - 2620 5020 - 5564 5564 - 5020 6232 - 6368 6368 - 6232 10744 - 10856 10856 - 10744 12285 - 14595 14595 - 12285 17296 - 18416 18416 - 17296 63020 - 76084 66928 - 66992 66992 - 66928 67095 - 71145 69615 - 87633 71145 - 67095 76084 - 63020 79750 - 88730 87633 - 69615 88730 - 79750 100485 - 124155 122265 - 139815 122368 - 123152 123152 - 122368 124155 - 100485 139815 - 122265 141664 - 153176 142310 - 168730 153176 - 141664 168730 - 142310 171856 - 176336 176272 - 180848 176336 - 171856 180848 - 176272 185368 - 203432 196724 - 202444 202444 - 196724 203432 - 185368 280540 - 365084 308620 - 389924 319550 - 430402 356408 - 399592 365084 - 280540 389924 - 308620 399592 - 356408 430402 - 319550 437456 - 455344 455344 - 437456 469028 - 486178 486178 - 469028 503056 - 514736 514736 - 503056 522405 - 525915 525915 - 522405 600392 - 669688 609928 - 686072 624184 - 691256 635624 - 712216 643336 - 652664 652664 - 643336 667964 - 783556 669688 - 600392 686072 - 609928 691256 - 624184 712216 - 635624 726104 - 796696 783556 - 667964 796696 - 726104 802725 - 863835 863835 - 802725 879712 - 901424 898216 - 980984 901424 - 879712 947835 - 1125765 980984 - 898216 998104 - 1043096 1043096 - 998104 1077890 - 1099390 1099390 - 1077890 1125765 - 947835 1154450 - 1189150 1156870 - 1292570 1175265 - 1438983 1185376 - 1286744 1189150 - 1154450 1280565 - 1340235 1286744 - 1185376 1292570 - 1156870 1328470 - 1483850 1340235 - 1280565 1358595 - 1486845 1392368 - 1464592 1438983 - 1175265 1464592 - 1392368 1466150 - 1747930 1468324 - 1749212 1483850 - 1328470 1486845 - 1358595 1511930 - 1598470 1598470 - 1511930 1669910 - 2062570 1747930 - 1466150 1749212 - 1468324 1798875 - 1870245 1870245 - 1798875 2062570 - 1669910 2082464 - 2090656 2090656 - 2082464 2236570 - 2429030 2429030 - 2236570 2652728 - 2941672 2723792 - 2874064 2728726 - 3077354 2739704 - 2928136 2802416 - 2947216 2803580 - 3716164 2874064 - 2723792 2928136 - 2739704 2941672 - 2652728 2947216 - 2802416 3077354 - 2728726 3276856 - 3721544 3606850 - 3892670 3716164 - 2803580 3721544 - 3276856 3786904 - 4300136 3805264 - 4006736 3892670 - 3606850 4006736 - 3805264 4238984 - 4314616 4246130 - 4488910 4259750 - 4445050 4300136 - 3786904 4314616 - 4238984 4445050 - 4259750 4482765 - 5120595 4488910 - 4246130 4532710 - 6135962 4604776 - 5162744 5120595 - 4482765 5123090 - 5504110 5147032 - 5843048 5162744 - 4604776 5232010 - 5799542 5357625 - 5684679 5385310 - 5812130 5459176 - 5495264 5495264 - 5459176 5504110 - 5123090 5684679 - 5357625 5726072 - 6369928 5730615 - 6088905 5799542 - 5232010 5812130 - 5385310 5843048 - 5147032 5864660 - 7489324 6088905 - 5730615 6135962 - 4532710 6329416 - 6371384 6369928 - 5726072 6371384 - 6329416 6377175 - 6680025 6680025 - 6377175 6955216 - 7418864 6993610 - 7158710 7158710 - 6993610 7275532 - 7471508 7288930 - 8221598 7418864 - 6955216 7471508 - 7275532 7489112 - 7674088 7489324 - 5864660 7577350 - 8493050 7674088 - 7489112 7677248 - 7684672 7684672 - 7677248 7800544 - 7916696 7850512 - 8052488 7916696 - 7800544 8052488 - 7850512 8221598 - 7288930 8262136 - 8369864 8369864 - 8262136 8493050 - 7577350 8619765 - 9627915 9071685 - 9498555 9199496 - 9592504 9339704 - 9892936 9363584 - 9437056 9437056 - 9363584 9498555 - 9071685 9592504 - 9199496 9627915 - 8619765 9892936 - 9339704 |
|
11
luckyrayyy 2020-03-23 17:32:12 +08:00
写了个单线程的，感觉这个多线程有点麻烦，算了 16 秒，结果 462 个，跟楼主有点出入，下班再看是不是哪里错了。
https://gist.github.com/Beritra/4e1a4440bf8203a7df1a8ba5f2f8f5ab |
|
12
luckyrayyy 2020-03-23 17:36:34 +08:00
既然排除自身的话，友好数应该是偶数个吧？楼主怎么算出来是奇数？
|
|
13
YUX OP @luckyrayyy #12 虽然友好数是成对出现的 但是如果一对友好数中有一个超过限制(1 亿) 那这个数就不能算作小于一亿的友好数
|
|
14
luckyrayyy 2020-03-23 18:00:13 +08:00
@YUX 噢噢，原来如此，那应该是我漏掉了几个你说的这种情况的。
|
 |
15
crella 2020-03-23 18:18:52 +08:00
好奇楼主为什么研究这些“数学题”。
|
|
17
crella 2020-03-23 18:26:47 +08:00
个人微小的意见，某些奥数题目真的浪费时间。
在 nga 看到的题目：15*15 的棋盘上布满黑棋和白旗，其中黑棋的数量等于白棋的数量+1 。求黑棋不存在五子相连的概率。注：相连的方向可以是水平线、竖直线、斜线。 |
|
18
YUX OP  1
python 服务器上 77.49 秒 今天研究了一下 numba，‘一行代码真的速度翻了十倍’ https://numba.pydata.org/
https://gist.github.com/YUX-IO/426ce33562c15fe6a56a84afc6d20987 |
 |
19
7Sasuke7L 2020-03-23 18:33:54 +08:00 via Android
数学系是偏计算类的吧，基础数学一般不研究这种问题
|
|
20
7Sasuke7L 2020-03-23 18:34:30 +08:00 via Android
简单提个建议，这叫因子，或者叫正整数因子，而不是除数。
|
 |
21
Ultraman 2020-03-23 18:37:52 +08:00 via iPhone
这个问题实实在在让我认识到了电脑性能的差距。。。
算了好久才算了不到 200 个。。。 |
|
24
Ultraman 2020-03-23 19:01:25 +08:00
@YUX #23 C 语言。376s 才跑完前 1000 个，而且才算出来 200 个结果，还不知道哪里错了。感觉 c 语言白学了 QAQ
https://pastebin.com/embed_js/F1AiPK9F |
|
26
input2output 2020-03-23 19:15:12 +08:00
用 go 写了一个，速度还行，30 几秒的样子，就是不知道哪里出错了，算出来 432 个
|
|
27
YUX OP 1
@input2output #26 前一千万是 208 个么？
|
 |
28
shm7 2020-03-23 19:18:16 +08:00 via iPhone
是不是可以把质数算出来，然后用小的非质数做 线性规划
|
|
29
input2output 2020-03-23 19:21:10 +08:00
@input2output #26 把 uint32 改成 uint64 就好了，就是慢了好多；算下来是 462 ？
和 @luckyrayyy #11 一样 如果 a 可以等于 b，那算下来就是 467 了 |
|
31
luckyrayyy 2020-03-23 19:34:56 +08:00 1
@input2output 你看下楼主回复我的，不是因为相等，是因为 a 小于一亿，b 大于一亿这种情况没算。
|
 |
32
litmxs 2020-03-23 23:49:20 +08:00 1
10s, 500Mb 内存
C++多线程, 上古 i5 笔记本 和昨天一样的思路写的, 参照这篇文章进行了优化: https://www.xarg.org/puzzle/project-euler/problem-21/ 答案是 462 个(入伙可以相等的话那就是 467 个 优化空间还很大, 应该还可以优化到 5s 内 https://gist.github.com/LiTianxiong/40263593e9464a205e567b4cf1d4314b |
 |
33
ksedz 2020-03-24 00:12:41 +08:00 2
$ time ./main
467 real 0m7.801s user 0m7.579s sys 0m0.228s 先算出 1 亿以内所有质数，然后对幂次做深搜，占内存有点大，2G 多 https://gist.github.com/shapled/e21a6d5ecd8129a6a7bccc84d1f67b9a |
 |
34
123444a 2020-03-24 00:46:13 +08:00 via Android
分解素因子即可，很多年前的题目了
|
 |
35
liyunlong41 2020-03-24 01:03:34 +08:00 via iPhone
@Ultraman 应该是意识到算法的差距吧
|
|
36
liyunlong41 2020-03-24 01:18:43 +08:00
应该是有相应的算法来求解的，但是我不会~，直接暴力求的…，1 亿以内 462 个，golang，19 秒，790M 内存。
func TestDn(t *testing.T) { const N = 1e8 var dn = make([]int, N+1) for i := 2; i+i <= N; i++ { for j := i << 1; j <= N; j += i { //fmt.Println(j) dn[j] += i } } count := 0 for a := 2; a <= N; a++ { b := dn[a] + 1 if b != a { if b <= N && dn[b]+1 == a { //fmt.Println(a, b) count++ } } } fmt.Println("count:", count) } |
|
37
123444a 2020-03-24 01:25:24 +08:00 via Android
@liyunlong41 这是 acm 题，19s 通不过的
|
|
38
liyunlong41 2020-03-24 01:34:57 +08:00 via iPhone
@123444a 思想交流而已，不用这么认真。再说能跑出数据来了，打表不随便过嘛。
|
|
39
123444a 2020-03-24 01:36:18 +08:00 via Android
@liyunlong41 没人告诉你止于 1 亿哦
|
|
40
123444a 2020-03-24 01:38:14 +08:00 via Android
最终就是要打表滴呵呵
|
 |
41
nomoon 2020-03-24 03:16:51 +08:00
楼主你这是在刷 project euler 么？
|
 |
43
wutiantong 2020-03-24 13:36:20 +08:00
我不能认同把这个叫做数学题，作为算法题这也挺无趣的。
|
 |
44
starqoq 2020-03-24 13:51:29 +08:00
首先用线性素数筛把所有素数都找出来，对于合数，也可以记录一个因子。
然后对于和数 d(X) = d(X/p) + p (p 是 X 的一个因子) 然后在扫一下满足 d(X)!=X && d(d(X))=X 即可 复杂度 O(n) |
 |
45
macg0406 2020-03-25 15:36:54 +08:00
先求 X 的所有因子之和，可以用递推方式求解，f(k) = f(m) * f(n), 如果 k = m * n，并且 m, n 互质。然后减去本身就得到了本题中的 d(x)。
time ./a.out 462 ./a.out 4.06s user 0.14s system 99% cpu 4.202 total 时间复杂度不超过 O(n logn)空间复杂度是 O(n) |
Select Language