--- id: 5900f4be1000cf542c50ffd1 title: 'Problema 338: Corte de papel de grade retangular' challengeType: 5 forumTopicId: 301996 dashedName: problem-338-cutting-rectangular-grid-paper --- # --description-- Você recebe uma folha retangular de papel de grade com dimensões em números inteiros $w$ × $h$. O espaçamento da grade é de 1. Quando cortamos as folhas ao longo das linhas da grade em duas partes e reorganizamos essas peças sem sobreposição, podemos criar novos retângulos com dimensões diferentes. Por exemplo, a partir de uma folha com dimensões 9 × 4, podemos fazer retângulos com dimensões 18 × 2, 12 × 3 e 6 × 6 cortando e reorganizando como vemos abaixo: folha com dimensões 9 x 4 cortada em três maneiras diferentes para criar retângulos com dimensões 18 x 2, 12 x 3 e 6 x 6 Da mesma forma, a partir de uma folha com dimensões 9 × 8, podemos fazer retângulos com dimensões 18 × 4 e 12 × 6. Para um par $w$ e $h$, considere $F(w, h)$ como o número de retângulos distintos que podem ser feitos a partir de uma folha com dimensões $w$ × $h$. Por exemplo, $F(2, 1) = 0$, $F(2, 2) = 1$, $F(9, 4) = 3$ e $F(9, 8) = 2$. Observe que os retângulos congruentes com o inicial não são contados em $F(w, h)$. Observe também que os retângulos com dimensões $w$ × $h$ e as dimensões $h$ × $w$ não são considerados distintos. Para um número inteiro $N$, considere $G(N)$ como a soma de $F(w, h)$ para todos os pares $w$ e $h$ que satisfazem $0 < h ≤ w ≤ N$. Podemos verificar que $G(10) = 55$, $G({10}^3) = 971.745$ e $G({10}^5) = 9.992.617.687$. Encontre $G({10}^{12})$. Dê sua resposta modulo ${10}^8$. # --hints-- `cuttingRectangularGridPaper()` deve retornar `15614292`. ```js assert.strictEqual(cuttingRectangularGridPaper(), 15614292); ``` # --seed-- ## --seed-contents-- ```js function cuttingRectangularGridPaper() { return true; } cuttingRectangularGridPaper(); ``` # --solutions-- ```js // solution required ```