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