Files

125 lines
2.9 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

---
id: 5900f3cc1000cf542c50fede
title: '問題 95友好的數鏈'
challengeType: 5
forumTopicId: 302212
dashedName: problem-95-amicable-chains
---
# --description--
一個數的真因子是除自身以外的其他因子。 例如28 的真因子是 1、2、4、7 和 14。 由於這些真因子之和等於 28我們稱 28 爲完全數,又稱完美數或完備數。
有趣的是220 的真因子之和爲 284而 284 的真因子之和爲 220形成了一條兩個數構成的鏈。 因此220 和 284 被稱爲友好數對。
也許更長的鏈條鮮爲人知。 例如,從 12496 開始,可以形成一條五個數字的數鏈:
$$ 12496 → 14288 → 15472 → 14536 → 14264 \\,(→ 12496 → \cdots) $$
由於該鏈返回其起始點,因此稱爲友好數鏈。
找出最長友好數鏈中的最小數字,要求該鏈中的每一個數字均不能超過給定的 `limit`
# --hints--
`amicableChains(300)` 應該返回一個數字。
```js
assert(typeof amicableChains(300) === 'number');
```
`amicableChains(300)` 應該返回 `220`
```js
assert.strictEqual(amicableChains(300), 220);
```
`amicableChains(15000)` 應該返回 `220`
```js
assert.strictEqual(amicableChains(15000), 220);
```
`amicableChains(100000)` 應該返回 `12496`
```js
assert.strictEqual(amicableChains(100000), 12496);
```
`amicableChains(1000000)` 應該返回 `14316`
```js
assert.strictEqual(amicableChains(1000000), 14316);
```
# --seed--
## --seed-contents--
```js
function amicableChains(limit) {
return true;
}
amicableChains(300);
```
# --solutions--
```js
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;
}
```