125 lines
3.6 KiB
Markdown
125 lines
3.6 KiB
Markdown
---
|
||
id: 5900f3cc1000cf542c50fede
|
||
title: 'Задача 95: Ланцюжки дружніх чисел'
|
||
challengeType: 5
|
||
forumTopicId: 302212
|
||
dashedName: problem-95-amicable-chains
|
||
---
|
||
|
||
# --description--
|
||
|
||
Власними дільниками числа є всі його дільники, окрім самого числа. Наприклад, власними дільниками числа 28 є 1, 2, 4, 7 і 14. Оскільки сума цих дільників дорівнює 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;
|
||
}
|
||
```
|