Line of Light

二次元の場合

以下のような問題を考えます。

• 辺の長さが $1$ である正方形 $ABCD$ があります。
  $A$ の座標は $(0,0)$、$B$ の座標は $(1,0)$、$C$ の座標は $(1,1)$ であり、正方形のそれぞれの辺には厚さを考慮しない鏡があります。
  点 $A$ から 正方形の辺上にある点 $P(x,y)(0<x,y)$ へ光線を発射することを考えます。このとき、光線は辺 $AB$ で $a$ 回以下、面 $AD$ で $b$ 回以下反射した後、いずれかの頂点で消えました。 このとき、条件を満たす全ての正の実数 $(x,y)$ の組の数を求めてください。

  また、この光線は以下の性質を満たします。

  • 入射角と反射角が等しい。
  • 辺や頂点に光線が当たった場合、光線は消える。

このような問題では、光の道筋を展開すると見通しが良くなる場合があります。実際に光の道筋を展開したものは以下のようになります。

すると、点 $A$ から発射され、いずれかの頂点で消える光の道筋は、下の図の頂点 $A$ からいずれかの点へ向かう直線に対応していることが分かります。
右上の点 $A$ から下へ $x$ ,右へ $y$ 進んだ地点を $(x,y)$ として、$(0,0)$ と $(x,y)$ を結ぶ線分と対応する光の道筋を考えるとき、光が辺 $CD$ で反射する回数は $\left\lfloor \dfrac{x}{2} \right\rfloor$ であることが分かります。また、その他の辺についても同様に求めることが出来ます。

ただし、$x$ と $y$ が互いに素ではない場合、つまり上の図の黒い点線などの場合、線分の途中に点 $C$ があるので、頂点に当たっているが光が消えないということが起こってします。よって、$x$ と $y$ が互いに素である必要があります。

以上の考察から、この問題は以下の問題に帰着されます。

• 次の条件を満たす正整数 $x,y$ の組の数を求めよ。
  • $\gcd(x,y)=1,x \leq 2a+2,y \leq 2b+2$

実は、この問題は包除原理を使うことでこの問題を解くことが出来ます。
$f(x)$ を $\gcd(i,j)=x,i \leq 2a+2,j \leq 2b+2$ を満たす正整数 $(i,j)$ の組の個数とすると、
$f(n)=\lfloor\frac{2a+2}{n}\rfloor\lfloor\frac{2b+2}{n}\rfloor-f(2n)-f(3n)-\cdots$ であることが分かります。
よって、$f(n)$ を値が大きい方から計算することによってこの問題を解くことが出来ました。

三次元の場合

二次元の場合と同じ議論をすることにより、この問題は以下の問題に帰着されます。
$\gcd(x,y,z)=1$ を条件とすると光線が辺に当たってしまうものを数えてしまっていることに注意してください。

• 次の条件を満たす正整数 $x,y,z$ の組の数を求めよ。
  • $\gcd(x,y)=\gcd(x,z)=\gcd(y,z)=1,x \leq 2a+2,y \leq 2b+2,z \leq 2c+2$

しかし、このままでは明らかに実行時間制限に間に合いません。
そこで、先程の方法を応用することを考えます。
まず、$A_n$ を$\gcd(x,y)=1,\text{lcm}(x,y)=n,x \leq 2a+2,y \leq 2b+2$ を満たす正整数 $(x,y)$ の組の個数とする数列 $A$ のそれぞれの値を求め、
二次元の場合の $f(x)$ の定義を
$\gcd(i,j)=x,i \leq 2a+2,j \leq 2b+2$ を満たす正整数 $(i,j)$ についての $A_i$ の総和とすると、二次元の場合と同じような式でこれを計算することが出来ます。
これは二次元の場合の条件を満たす $(x,y)$ の個数を先に計算した後、 $\gcd(i,j)=\gcd(i,k)=1$ であれば $\gcd(i,\text{lcm}(j,k))=1$ であり、
その逆も成立する事実を利用することによって導き出すことが出来ます。
よって、この問題を解くことが出来ました。