SRM500 Div2 Hard(1000) GeometricProgressions

GeometricProgressions

積なので素因数分解が簡単に計算できる。素因数の個数を覚えておく。コメントアウトのように書いたらメモリ不足で落ちた。b2*q2²以降は、b2*q2¹と異なりS1に含まれないものの個数を数えるだけにしたら通った。

#include <set>
#include <map>
using namespace std;

//  素因数分解
map<int,int>fact( int n )
{
    map<int,int>r;
    int p=2;
    while(p*p<=n)
        if(n%p==0)r[p]++,n/=p;
        else p++;
    if(n>1)r[n]++;
    return r;
}

class GeometricProgressions{public:
int count( int b1, int q1, int n1, int b2, int q2, int n2 )
{
    map<int,int> f0; f0[0] = -1;    //  0を表す
    map<int,int> b1f = b1>0 ? fact(b1) : f0;
    map<int,int> q1f = q1>0 ? fact(q1) : f0;
    map<int,int> b2f = b2>0 ? fact(b2) : f0;
    map<int,int> q2f = q2>0 ? fact(q2) : f0;

    set<map<int,int> > S;
    
    S.insert(b1f);
    for ( int i=1; i<n1; i++ )
    {
        if ( b1f!=f0 && q1f!=f0 )
            for ( map<int,int>::iterator it=q1f.begin(); it!=q1f.end(); it++ )
                b1f[it->first] += it->second;
        else
            b1f = f0;
        S.insert(b1f);
    }

    S.insert(b2f);
    int c = 0;
    map<int,int> b2f1;
    for ( int i=1; i<n2; i++ )
    {
        if ( b2f!=f0 && q2f!=f0 )
            for ( map<int,int>::iterator it=q2f.begin(); it!=q2f.end(); it++ )
                b2f[it->first] += it->second;
        else
            b2f = f0;

        if ( i==1 )
            S.insert(b2f),
            b2f1 = b2f;
        else
            if ( b2f!=b2f1 && S.count(b2f)==0 )
                c++;
    }

    return (int)S.size() + c;

    /*
    S.insert(b2f);
    for ( int i=1; i<n2; i++ )
    {
        if ( b2f!=f0 && q2f!=f0 )
            for ( map<int,int>::iterator it=q2f.begin(); it!=q2f.end(); it++ )
                b2f[it->first] += it->second;
        else
            b2f = f0;
        S.insert(b2f);
    }

    return (int)S.size();
    */
}};