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