2018-10-10 18:03:03 -04:00
|
|
|
|
---
|
|
|
|
|
id: 5900f3cc1000cf542c50fede
|
2021-09-30 07:29:50 -07:00
|
|
|
|
title: '问题 95:友好的数链'
|
2018-10-10 18:03:03 -04:00
|
|
|
|
challengeType: 5
|
2021-02-06 04:42:36 +00:00
|
|
|
|
forumTopicId: 302212
|
2021-01-13 03:31:00 +01:00
|
|
|
|
dashedName: problem-95-amicable-chains
|
2018-10-10 18:03:03 -04:00
|
|
|
|
---
|
|
|
|
|
|
2020-12-16 00:37:30 -07:00
|
|
|
|
# --description--
|
2018-10-10 18:03:03 -04:00
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
一个数的真因子是除自身以外的其他因子。 例如,28 的真因子是 1、2、4、7 和 14。 由于这些真因子之和等于 28,我们称 28 为完全数,又称完美数或完备数。
|
2021-02-06 04:42:36 +00:00
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
有趣的是,220 的真因子之和为 284,而 284 的真因子之和为 220,形成了一条两个数构成的链。 因此,220 和 284 被称为友好数对。
|
2021-02-06 04:42:36 +00:00
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
也许更长的链条鲜为人知。 例如,从 12496 开始,可以形成一条五个数字的数链:
|
2021-02-06 04:42:36 +00:00
|
|
|
|
|
2021-07-15 13:04:11 +05:30
|
|
|
|
$$ 12496 → 14288 → 15472 → 14536 → 14264 \\,(→ 12496 → \cdots) $$
|
2021-02-06 04:42:36 +00:00
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
由于该链返回其起始点,因此称为友好数链。
|
2021-02-06 04:42:36 +00:00
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
找出最长友好数链中的最小数字,要求该链中的每一个数字均不能超过给定的 `limit`。
|
2018-10-10 18:03:03 -04:00
|
|
|
|
|
2020-12-16 00:37:30 -07:00
|
|
|
|
# --hints--
|
2018-10-10 18:03:03 -04:00
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
`amicableChains(300)` 应该返回一个数字。
|
2021-02-06 04:42:36 +00:00
|
|
|
|
|
|
|
|
|
```js
|
2021-07-15 13:04:11 +05:30
|
|
|
|
assert(typeof amicableChains(300) === 'number');
|
2021-02-06 04:42:36 +00:00
|
|
|
|
```
|
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
`amicableChains(300)` 应该返回 `220`。
|
2018-10-10 18:03:03 -04:00
|
|
|
|
|
|
|
|
|
```js
|
2021-07-15 13:04:11 +05:30
|
|
|
|
assert.strictEqual(amicableChains(300), 220);
|
|
|
|
|
```
|
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
`amicableChains(15000)` 应该返回 `220`。
|
2021-07-15 13:04:11 +05:30
|
|
|
|
|
|
|
|
|
```js
|
|
|
|
|
assert.strictEqual(amicableChains(15000), 220);
|
|
|
|
|
```
|
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
`amicableChains(100000)` 应该返回 `12496`。
|
2021-07-15 13:04:11 +05:30
|
|
|
|
|
|
|
|
|
```js
|
|
|
|
|
assert.strictEqual(amicableChains(100000), 12496);
|
|
|
|
|
```
|
|
|
|
|
|
2021-09-30 07:29:50 -07:00
|
|
|
|
`amicableChains(1000000)` 应该返回 `14316`。
|
2021-07-15 13:04:11 +05:30
|
|
|
|
|
|
|
|
|
```js
|
|
|
|
|
assert.strictEqual(amicableChains(1000000), 14316);
|
2018-10-10 18:03:03 -04:00
|
|
|
|
```
|
|
|
|
|
|
2021-01-13 03:31:00 +01:00
|
|
|
|
# --seed--
|
|
|
|
|
|
|
|
|
|
## --seed-contents--
|
|
|
|
|
|
|
|
|
|
```js
|
2021-07-15 13:04:11 +05:30
|
|
|
|
function amicableChains(limit) {
|
2021-01-13 03:31:00 +01:00
|
|
|
|
|
|
|
|
|
return true;
|
|
|
|
|
}
|
|
|
|
|
|
2021-07-15 13:04:11 +05:30
|
|
|
|
amicableChains(300);
|
2021-01-13 03:31:00 +01:00
|
|
|
|
```
|
|
|
|
|
|
2020-12-16 00:37:30 -07:00
|
|
|
|
# --solutions--
|
2020-08-13 17:24:35 +02:00
|
|
|
|
|
2021-01-13 03:31:00 +01:00
|
|
|
|
```js
|
2021-07-15 13:04:11 +05:30
|
|
|
|
function amicableChains(limit) {
|
|
|
|
|
function getSmallestMember(chain) {
|
|
|
|
|
let smallest = chain[0];
|
|
|
|
|
for (let i = 1; i < chain.length; i++) {
|
|
|
|
|
if (smallest > chain[i]) {
|
|
|
|
|
smallest = chain[i];
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
return smallest;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
function getFactorsSums(limit) {
|
|
|
|
|
const factorsSums = new Array(limit + 1).fill(1);
|
|
|
|
|
for (let i = 2; i <= limit / 2; i++) {
|
|
|
|
|
for (let j = 2 * i; j <= limit; j += i) {
|
|
|
|
|
factorsSums[j] += i;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
return factorsSums;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
const factorsSums = getFactorsSums(limit);
|
|
|
|
|
const checkedNumbers = new Set();
|
|
|
|
|
|
|
|
|
|
let longestChain = 0;
|
|
|
|
|
let smallestMember = 0;
|
|
|
|
|
for (let i = 0; i <= limit; i++) {
|
|
|
|
|
const curChain = [];
|
|
|
|
|
let curNumber = i;
|
|
|
|
|
while (!checkedNumbers.has(curNumber) && factorsSums[curNumber] <= limit) {
|
|
|
|
|
curNumber = factorsSums[curNumber];
|
|
|
|
|
|
|
|
|
|
const chainStart = curChain.indexOf(curNumber);
|
|
|
|
|
if (chainStart === -1) {
|
|
|
|
|
curChain.push(curNumber);
|
|
|
|
|
continue;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
const chainLength = curChain.length - chainStart;
|
|
|
|
|
if (chainLength > longestChain) {
|
|
|
|
|
longestChain = chainLength;
|
|
|
|
|
smallestMember = getSmallestMember(curChain.slice(chainStart));
|
|
|
|
|
}
|
|
|
|
|
break;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (let j = 0; j < curChain.length; j++) {
|
|
|
|
|
checkedNumbers.add(curChain[j]);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return smallestMember;
|
|
|
|
|
}
|
2021-01-13 03:31:00 +01:00
|
|
|
|
```
|