## 2011年3月21日月曜日

### SRM BrushUp: GeometricProgressions (500 div2 Hard)

しかし、div 2はいまいち納得できない結果となった。Hardの問題を解いてsystem testをpassしている人たちの回答が、なんか微妙。。。
ハッシュを使ってるんですけど、たまたまsystem test通っただけで、正規の解答とは異なるのでは？？という疑問がちらほら。。

てことで、がんばって解いてみました。

こんな感じっす。。

`#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)typedef map<int, int> MII;set<MII>seq;class GeometricProgressions {public:    int count(int b1, int q1, int n1, int b2, int q2, int n2) {        if (!seq.empty())            seq.clear();        setFactorizedSeq(b1, q1, n1);        return checkFactorizedSeq(b2, q2, n2) + seq.size();    }private:    MII nextElemFactors(MII curr, MII mul) {        EACH(itr, mul) {            if (curr.count(itr->first)) {                if (itr->first != 0 && itr->first != 1)                    curr[itr->first] += itr->second;            }            else {                if (itr->first == 0) {                    curr.clear();                    curr[0] = 1;                }                else if (itr->first != 1)                    curr[itr->first] = itr->second;            }        }        return curr;    }    int checkFactorizedSeq(int b, int q, int n) {        int ret = 0;        MII facb = factorize(b);        MII facq = factorize(q);        FOR (i, 0, n) {            if (!seq.count(facb)) ++ret;            if (!b) break;            MII fact = nextElemFactors(facb, facq);            if (fact == facb) break;            facb = fact;        }        return ret;    }    void setFactorizedSeq(int b, int q, int n) {        MII facb = factorize(b);        MII facq = factorize(q);        FOR (i, 0, n) {            seq.insert(facb);            if (!b) break;            facb = nextElemFactors(facb, facq);        }    }    MII factorize(int n) {        MII factors;        if (n == 0 || n == 1) {            factors[n] = 1;            return factors;        }        FOR (i, 2, sqrt(n)+1)            while (n % i == 0) {                if (factors.count(i)) factors[i]++;                else factors[i] = 1;                n /= i;            }        if (n != 1)            factors[n] = 1;        return factors;    }};`