紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

Project Euler 504 Square on the Inside

projecteuler.net

1<=a,b,c,d<=mに対して(a,0)(0,b)(-c,0)(0,-d)で囲まれた四角形内部の格子点の個数(境界を含まない)は
{\displaystyle
\frac{ab+bc+cd+da-gcd(a,b)-gcd(b,c)-gcd(c,d)-gcd(d,a)}{2}+1
}

証明:
例えばa=4,b=2として下の図形を考える.
f:id:umashika5555:20161123014957p:plain
まずa*bの長方形の格子点の個数を考える.すると(x軸の点5個)*(y軸の点3個)=15個である.
これは(a+1)*(b+1)を計算している.
次に境界線上の点を数える. この直線上で格子点を通るのはgcd(a,b)+1個.
これらを同様に全てに適応すると
{\displaystyle
\frac{(a+1)(b+1)-gcd(a,b)-1+(b+1)(c+1)-gcd(b,c)-1+\\(c+1)(d+1)-gcd(c,d)-1+(d+1)(a+1)-gcd(d,a)-1}{2}\\-(a+b+c+d)+1
}

 -(a+b+c+d)+1は重複して数えている点を1回分引いている. それだけだと原点が入らなくなるので+1


参考にしたページ
examist.jp