SRM 626

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;
}
};