読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 504 / 四角内部の平方

頂点が以下のような座標軸の格子点に置かれている四辺形を ABCD としよう。

A(a, 0), B(0, b), C(−c, 0), D(0, −d)

1≤a,b,c,d≤ m であり,a,b,c,d,m は整数とする。

m=4 のとき, ABCD を描く方法の数がちょうど 256 個ある。その 256 個の四辺形のうち厳密に平方数個の格子点を含む(訳注:四辺形の辺の上に位置する格子点は含まない)ものは 42 個ある。

m=100 のとき,厳密に平方数個の格子点を含む四辺形 ABCD は何個あるか?

Problem 504 - Project Euler


ピックの定理を使います。格子点を結んでできる多角形の面積をSとして,多頂点の内部にI個,辺上にB個の格子点をもつとすると次の式が成り立ちます。
ピックの定理 - Wikipedia

 S=I+\dfrac{B}{2}-1

この問題では面積は S=(a+c)(b+d)/2
また,辺AB上には端点を含めて gcd[a,b]+1 個の格子点があります。他の辺も同様です。頂点のダブルカウント分を除くと

I=(a+c)(b+d)/2-(gcd[a,b]+gcd[b,c]+gcd[c,d]+gcd[d,a])+1

これが平方数になるような (a, b,c, d) の個数が答えです。計算してみた結果がこちら。30分もかかってしまいました。


さすがにこれはかかりすぎなので,Select しない(=リストを作らない)方法でやってみました。こちらは11分。1分の壁はかなり遠いです。