freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/project-euler/problem-338-cutting-rectangular-grid-paper.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5900f4be1000cf542c50ffd1	Задача 338: Вирізання прямокутної сітчастої сітки	5	301996	problem-338-cutting-rectangular-grid-paper

--description--

Дано прямокутний аркуш паперу в решітку з цілочисельними розмірами w × h. Відстань між ґратками дорівнює 1.

Якщо розрізати аркуш по лініях ґратки на дві частини та переставити їх так, щоб вони не перекривали одне одного, можна отримати ще один прямокутник з іншими розмірами.

До прикладу, розрізавши та переставивши частинки аркуша паперу з розмірами 9 × 4 так, як показано нижче, можна зробити прямокутник зі сторонами 18 × 2, 12 × 3 та 6 × 6:

Схожим чином із листка 9 × 8 вийде прямокутник на 18 × 4 та 12 × 6.

Для пари w та h, нехай F(w, h) — та кількість прямокутників, яку можна отримати з аркуша паперу розміром w × h. Наприклад, F(2, 1) = 0, F(2, 2) = 1, F(9, 4) = 3 та F(9, 8) = 2. Зверніть увагу на те, що прямокутники, що збігаються з вихідним, не враховуються в F(w, h). До того ж прямокутники з розмірами w × h та h × w — вважаються однаковими.

Для цілого числа N, нехай G(N) — це сума F(w, h) для всіх пар w та h, яка задовольняє умову 0 < h ≤ w ≤ N. Можна перевірити, що G(10) = 55, G({10}^3) = 971\\,745 та G({10}^5) = 9\\,992\\,617\\,687.

Знайдіть G({10}^{12}). Надайте відповідь за модулем {10}^8.

--hints--

cuttingRectangularGridPaper() має повернути 15614292.

assert.strictEqual(cuttingRectangularGridPaper(), 15614292);

--seed--

--seed-contents--

function cuttingRectangularGridPaper() {

  return true;
}

cuttingRectangularGridPaper();

--solutions--

// solution required