Line of Light(没ver)

2 secs 1024 MB
Magentor's icon Magentor

解説はまだ未完成です

二次元の場合

09contest-1

図のように、光の道筋を展開することを考えます。 すると、点 AA から発射され、いずれかの頂点で消える光の道筋は、下の図の頂点Aからいずれかの点へ向かう直線に対応していることが分かります。
右上の点 AA から下へ xx ,右へ yy 進んだ地点を (x,y)(x,y) として、(0,0)(0,0)(x,y)(x,y) を結ぶ線分と対応する光の道筋を考えるとき、光が辺 CDCD で反射する回数は x2\left\lfloor \dfrac{x}{2} \right\rfloor であることが分かります。また、その他の辺についても同様に求めることが出来ます。
ただし、xxyy が互いに素ではない場合、つまり上の図の黒い点線などの場合、線分の途中に点 CC があるので、頂点に当たっているが光が消えないということが起こってします。よって、xxyy が互いに素である必要があります。

三次元の場合

二次元の場合と同じ議論をすることにより、この問題は以下の問題に帰着されます。

  • 次の条件を満たす正整数 x,y,zx,y,z の組について、 x2Xy2Yz2Z{\left\lfloor \dfrac{x}{2} \right\rfloor}^{X}{\left\lfloor \dfrac{y}{2} \right\rfloor}^{Y}{\left\lfloor \dfrac{z}{2} \right\rfloor}^{Z} の総和を求めよ。
    • gcd(x,y)=gcd(x,z)=gcd(y,z)=1,x2a+2,y2b+2,z2c+2\gcd(x,y)=\gcd(x,z)=\gcd(y,z)=1,x \leq 2a+2,y \leq 2b+2,z \leq 2c+2

しかし、このままでは計算量が O(abclogXYZ)O(abc\log{XYZ}) となり、明らかに実行時間制限に間に合いません。
そこで、長さが max(2a+2,2b+2)\max(2a+2,2b+2)Ai=gcd(x,y)=1,lcm(x,y)=i(x2Xy2Y)A_i=\displaystyle\sum_{\gcd(x,y)=1,\text{lcm}(x,y)=i}{{ \bigg( \left\lfloor \dfrac{x}{2} \right\rfloor}^{X}{\left\lfloor \dfrac{y}{2} \right\rfloor}^{Y} \bigg)} である数列 AA を考えます。 この数列の各項は O(ablogXY)O(ab \log{XY}) で求められることが分かります。また、長さが 2c+22c+2Bi=i2ZB_i={\left\lfloor \dfrac{i}{2} \right\rfloor}^{Z} である数列 BB を用意します。
また、Ci=gcd(x,y)=iAxByC_i=\displaystyle\sum_{\gcd(x,y)=i}{A_xB_y} である数列 CC を考えます。このとき、求めるべき答えは C1C_1 となります。 このことは、gcd(lcm(x,y),z)=1gcd(lcm(x,y),z)=1 であれば gcd(x,y)=1,gcd(x,z)=1gcd(x,y)=1,gcd(x,z)=1 であることを利用し、実際に展開をすると求めるべき答えと一致していることが分かります。

数列 CC の値を計算することを考えます。 実は、数列から数列への関数 f(x)f(x)f(x)i=ijxjf(x)_i=\displaystyle\sum_{i|j}{x_j} で定めるとき、f(A)if(B)i=f(C)if(A)_{i} f(B)_{i}=f(C)_i が成立していることが分かります。 つまり、f(x)f(x) の逆関数を計算することが出来れば数列 CC の値を高速に計算できると分かります。これはエラトステネスの篩の要領で計算することにより求めることが出来ます。 これで、この問題を解くことが出来ました。計算量は O(ablog(abXY)+clog(cZ))O(ab\log(abXY)+c\log(cZ)) となり、十分高速だと分かります。