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

Posted by xiaodao
Category: 日常
Tags: 莫比乌斯反演