http://apps.topcoder.com/wiki/display/tc/SRM+626

## 900. ReflectiveRectangle

### Brief description:

。給定一個長 sideA 寬 sideB 的矩陣。。

從左下角發射一枚光線，要求恰好在牆壁反射 n 次後落入右上角，且中途不能經過 corner。。。

### Analysis:

首先 n 必須是偶數。。

設在橫軸與縱軸分別反彈 a, b 次

那麼平鋪後的長寬分別為 (a+1)sideA, (b+1)sideB。。。

a+b == n，gcd(a+1, b+1) = 1

——————

然後顯然是一個莫比烏斯反演。。

。。。

s2(n) = 1^2 + 2^2 + \ldots + n^2 = n*(n+1)*(2*n+1)/6 ... g(d) = [d | gcd(i, n-i)] * (i^2) = sqr(d) * s2(n/d); f(d) = [d = gcd(i, n-i)] * (i^2) ...

卧槽我真是蠢哭了。。我居然寫樸素的時候有一個 LL 沒加。。一直樣例沒出來。。。

。。。艹。瞬間數論白學了。。（速度寫一個樸素的策略本身是沒問題的。。。但是處理的太不謹慎了。。）

const int PMAX = 46341; vector<int> P; bitset<PMAX> isC; int mu[PMAX]; void sieve(){ mu[1] = 1; FOR(i, 2, PMAX){ if (!isC[i]) P.PB(i), mu[i] = -1; for (int j=0;j<SZ(P)&&i*P[j]<PMAX;++j){ isC[i*P[j]]=1; if (!(i%P[j])){ mu[i*P[j]] = 0; break; } else{ mu[i*P[j]] = -mu[i]; } } } } VII fac; void fact(int x){ int z = x; fac.clear(); ECH(it, P) if (!(x%*it)){ int c=1; x/=*it; while (!(x%*it)) x/=*it, ++c; fac.PB(MP(*it, c)); } if (x!=1) fac.PB(MP(x, 1)); } Int ans; int n; Int s2(Int n){ return n*(n+1)*(2*n+1)/6; } Int f(Int d){ return s2(d)*sqr(Int(n/d)); } void gao(int k = 0, int c = 0, int d = 1){ if (k == SZ(fac)){ if (c&1) ans -= f(n/d); else ans += f(n/d); } else{ gao(k+1, c, d); gao(k+1, c+1, d*fac[k].fi); } } class ReflectiveRectangle { public: int findSum(int sideA, int sideB, int n) { if (n&1) return 0; Int cof = ((LL)sideA*sideA+(LL)sideB*sideB)%MOD; ans = 0, n += 2, ::n = n; REP_1(a, n){ int b = n-a; if (gcd(a, b) != 1) continue; ans += sqr((Int)a); } //cout << "b: " << n << endl; //sieve(); fact(n); gao(); return ans * cof; } };