53 lines
1.9 KiB
Markdown
53 lines
1.9 KiB
Markdown
---
|
||
id: 5900f47f1000cf542c50ff91
|
||
title: 'Задача 274: Множники подільності'
|
||
challengeType: 5
|
||
forumTopicId: 301924
|
||
dashedName: problem-274-divisibility-multipliers
|
||
---
|
||
|
||
# --description--
|
||
|
||
Для кожного цілого числа $p > 1$ взаємно простого до 10, додатний множник подільності $m < p$ зберігає подільність на $p$ для наступної функції на будь-яке додатнє ціле число, $n$:
|
||
|
||
$f(n) = (\text{all but the last digit of} \\; n) + (\text{the last digit of} \\; n) \times m$
|
||
|
||
Тож, якщо $m$ – це множник подільності для $p$, то $f(n)$ ділиться на $p$ тоді і лише тоді, як $n$ ділиться на $p$.
|
||
|
||
(Коли $n$ набагато більше за $p$, $f(n)$ буде меншим за $n$ і повторне застосування $f$ подає тест на подільність множників для $p$.)
|
||
|
||
Наприклад, множник подільності для 113 – це 34.
|
||
|
||
Обидва $f(76275) = 7627 + 5 \times 34 = 7797$: 76275 і 7797 діляться на 113
|
||
|
||
Обидва $f(12345) = 1234 + 5 \times 34 = 1404$: 12345 і 1404 діляться на 113
|
||
|
||
Сума множників подільності для простих чисел, що взаємо прості до 10 й менші за 1000, дорівнює 39517. Яка сума множників подільності для простих чисел, що взаємо прості до 10 і менші за ${10}^7$?
|
||
|
||
# --hints--
|
||
|
||
`divisibilityMultipliers()` має повернути `1601912348822`.
|
||
|
||
```js
|
||
assert.strictEqual(divisibilityMultipliers(), 1601912348822);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function divisibilityMultipliers() {
|
||
|
||
return true;
|
||
}
|
||
|
||
divisibilityMultipliers();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|