RSS Feed

직사각형 모눈 종이 자르기

Problem 338

출제 일시 : 2021-06-23 00:04:51

직사각형 모양 w × h인 정수 단위의 모눈 종이가 있습니다. 격자 간격은 1입니다.
격자선을 따라 두 조각으로 잘라서 겹치지 않도록 다시 붙여 다른 모양의 새로운 직사각형을 만듭니다.

예를 들어, 모양 9 × 4의 종이로, 모양 18 × 2, 12 × 3, 6 × 6 세 가지 직사각형을 만들 수 있습니다. 아래와 같이 자르고 다시 붙입니다:

p338_gridpaper.gif

비슷하게, 모양 9 × 8의 종이로는, 모양 18 × 4와 12 × 6 의 두 직사각형을 만들 수 있습니다.

wh 쌍에 대하여, 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이 정수일 때, 범위 0 < hwN의 모든 wh쌍으로 계산한 F(w,h)의 합을 G(N)이라 합니다.
G(10) = 55, G(103) = 971745 그리고 G(105) = 9992617687 입니다.

G(1012)을 구하고 그 값을 108으로 나눈 나머지를 답으로 제출하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.