[中譯] ProjectEuler 465 Polar polygons

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者tml (流刑人形)時間11年前 (2014/04/17 04:55)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

465. Polar polygons http://projecteuler.net/problem=465 一個多邊形的核定義為在多邊形內部能看見所有邊界的點的集合。我們定義極多邊形為包含原點在核的內部（通過核邊界者不算）的多邊形。在這個題目中，多邊形的內角可以是平角，但是不能自交，且面積不得為0。作為例子，下圖中只有最左邊的可以稱為極多邊形。（第二、三、四張圖中，原點不在核的內部，而第五張圖的多邊形甚至完全沒有核。） http://projecteuler.net/project/images/p465_polygons.png

注意到第一張圖的多邊形其實有一個平角。令P(n)為所有極多邊形中，其坐標(x,y)的絕對值均不大於n的個數。注意到即使兩多邊形包含的面完全相同，只要有一條邊不同即視為相異。例如，由頂點[(0,0),(0,3),(1,1),(3,0)]圍出的多邊形和由頂點 [(0,0),(0,3),(1,1),(3,0),(1,0)]圍出的多邊形視為相異。例如，P(1) = 131、P(2) = 1648531、P(3) = 1099461296175以及 P(343) mod 1000000007 = 937293740。請求出P(7^13) mod 1000000007。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.2.129.155 ※ 文章網址: http://www.ptt.cc/bbs/puzzle/M.1397681706.A.F5A.html