SRM BrushUp: GeometricProgressions (500 div2 Hard)

昨日（おとといか。。）SRM 500があった。

記念すべき500回目ということで賞金付き。

しかし、div 2はいまいち納得できない結果となった。Hardの問題を解いてsystem testをpassしている人たちの回答が、なんか微妙。。。

ハッシュを使ってるんですけど、たまたまsystem test通っただけで、正規の解答とは異なるのでは？？という疑問がちらほら。。

私も、そう思います。確かに、実入力10^5程度に対して、{10^9}^2のサイズのhashを使えば衝突が起こることは非常にまれと言えますが。。。

納得いかん。。。

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

私の解法は、素因数分解を使用しています。一応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;
    }

};