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は通ったけど、あっているかは不明。。。

こんな感じっす。。

view plainprint?

1. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
2. #define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)  
3.   
4. typedef map<int, int> MII;  
5.   
6. set<MII>seq;  
7.   
8. class GeometricProgressions {  
9. public:  
10.     int count(int b1, int q1, int n1, int b2, int q2, int n2) {  
11.         if (!seq.empty())  
12.             seq.clear();  
13.   
14.         setFactorizedSeq(b1, q1, n1);  
15.   
16.         return checkFactorizedSeq(b2, q2, n2) + seq.size();  
17.     }  
18.   
19. private:  
20.     MII nextElemFactors(MII curr, MII mul) {  
21.         EACH(itr, mul) {  
22.             if (curr.count(itr->first)) {  
23.                 if (itr->first != 0 && itr->first != 1)  
24.                     curr[itr->first] += itr->second;  
25.             }  
26.             else {  
27.                 if (itr->first == 0) {  
28.                     curr.clear();  
29.                     curr[0] = 1;  
30.                 }  
31.                 else if (itr->first != 1)  
32.                     curr[itr->first] = itr->second;  
33.             }  
34.         }  
35.         return curr;  
36.     }  
37.   
38.     int checkFactorizedSeq(int b, int q, int n) {  
39.         int ret = 0;  
40.         MII facb = factorize(b);  
41.         MII facq = factorize(q);  
42.   
43.         FOR (i, 0, n) {  
44.             if (!seq.count(facb)) ++ret;  
45.             if (!b) break;  
46.   
47.             MII fact = nextElemFactors(facb, facq);  
48.             if (fact == facb) break;  
49.             facb = fact;  
50.         }  
51.         return ret;  
52.     }  
53.   
54.     void setFactorizedSeq(int b, int q, int n) {  
55.         MII facb = factorize(b);  
56.         MII facq = factorize(q);  
57.   
58.         FOR (i, 0, n) {  
59.             seq.insert(facb);  
60.             if (!b) break;  
61.             facb = nextElemFactors(facb, facq);  
62.         }  
63.     }  
64.   
65.     MII factorize(int n) {  
66.         MII factors;  
67.   
68.         if (n == 0 || n == 1) {  
69.             factors[n] = 1;  
70.             return factors;  
71.         }  
72.   
73.         FOR (i, 2, sqrt(n)+1)  
74.             while (n % i == 0) {  
75.                 if (factors.count(i)) factors[i]++;  
76.                 else factors[i] = 1;  
77.                 n /= i;  
78.             }  
79.         if (n != 1)  
80.             factors[n] = 1;  
81.   
82.         return factors;  
83.     }  
84.   
85. };  

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

};