Files

125 lines
2.9 KiB
Markdown
Raw Permalink Normal View History

---
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;
}
```