ProjectEuler 465 Polar polygons - 拼圖

Mia avatar
By Mia
at 2014-04-17T04:55

Table of Contents

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。

--
Tags: 拼圖

All Comments

ProjectEuler 464 Möbius function and

Hedy avatar
By Hedy
at 2014-04-17T04:31
464. Möbius function and intervals http://projecteuler.net/problem=464 莫比烏斯函數,記作μ(n)定義如下:  ‧μ(n) = (-1)^ω(n),如果n沒有任何平方數因子,其中ω(n)為n的質因數個數。  ‧μ(n) = 0,如果n ...

ProjectEuler 463 A weird recurrence re

Leila avatar
By Leila
at 2014-04-17T04:21
463. A weird recurrence relation http://projecteuler.net/problem=463 一函數f對所有正整數定義如下:  ‧f(1) = 1  ‧f(3) = 3  ‧f(2n) = f(n)  ‧f(4n+1) = 2f(2n+1) - f(n)  ‧ ...

ProjectEuler 462 Permutation of 3-smoo

Sierra Rose avatar
By Sierra Rose
at 2014-04-17T04:15
462. Permutation of 3-smooth numbers http://projecteuler.net/problem=462 一個數被稱為3-光滑數代表它是正整數且其質因數都不大於3。 給定一正整數N,定義S(N)為所有不大於N的3-光滑數的集合。 例如,S(20) = { 1, ...

文字獄 002

Elvira avatar
By Elvira
at 2014-04-15T22:18
規則:中文詞在改變聲調之後常會變成另一個詞,比如「文字」變成「蚊子」;     定義輕聲~四聲的五種聲調為0~4,則「文字」是24,「蚊子」是20。     透過題目給予的提示,猜出這兩個可互變的詞語,注意字有可能都不同。  例題:有一個二字詞,24用來溝通,20讓人紅腫。  答案:文字∕蚊子  題目:1 ...

文字獄 001

Olivia avatar
By Olivia
at 2014-04-15T12:37
昨天讀書時忽然想到一系列奇特的文字謎,姑且喚它為文字獄好了XD  規則:中文詞在改變聲調之後常會變成另一個詞,比如「文字」變成「蚊子」;     定義輕聲~四聲的五種聲調為0~4,則「文字」是24,「蚊子」是20。     透過題目給予的提示,猜出這兩個可互變的詞語,注意字有可能都不同。  例題:有一個二 ...