SRM 500 Div2 Hard : GeometricProgressions

問題概要 :
短いし分かりやすいので略

解法 :
素因数分解 + ローリングハッシュで通せたが怪しい気がしなくもない
愚直に値を計算すると当然オーバーフローするので、素因数分解してからq1,q2の各素因数の数だけを増やしていく感じにした
setにmapを詰めたところバッドアロックだったので、
mapの値をローリングハッシュで unsigned long long の値に変換してsetにつめたら通った

大きな値がでたら素因数分解 ( 師範代より )

コード :

typedef long long ll;
typedef unsigned long long ull;

const ull base = 1000000007ULL;

class GeometricProgressions {
public:

  map<ll,ll> prime_factor(ll n){
    map<ll,ll> ret;
    ret[1] = 1;
    for(ll i=2;i*i<=n;i++){
      while( n % i == 0LL ){
	++ret[i];
	n /= i;
      }
    }
    if( n != 1LL ) ret[n] = 1;
    return ret;
  }

  ull toHash(map<ll,ll> buf){
    ull tmp = 0;
    for(map<ll,ll>::iterator it = buf.begin(); it != buf.end(); it++ ){
      tmp *= base;
      tmp *= base;
      tmp += it->first;
      tmp *= base;
      tmp += it->second;
    }    
    return tmp;
  }

  int count(int b1, int q1, int n1, int b2, int q2, int n2) {
    map<ll,ll> pf,coef,buf;
    set<ull> S;
    pf   = prime_factor(b1);
    coef = prime_factor(q1);
    buf = pf;

    if( b1 == 0 ) {
      S.insert(0);
    } else if( q1 == 0 ){ 
      buf[1] = 1LL;
      buf[0] = 0LL;
      S.insert(toHash(buf));
      if( n1 > 1 ) S.insert(0);
    } else {
      rep(_,n1){
	buf[1] = 1LL;
	buf[0] = 0LL;
	S.insert(toHash(buf));
	for(map<ll,ll>::iterator it = coef.begin(); it != coef.end(); it++ ) {
	  buf[it->first] += it->second;
	  assert( buf[it->first] > 0 );
	}
      }
    }

    pf   = prime_factor(b2);
    coef = prime_factor(q2);
    buf = pf;
    if( b2 == 0 ) {
      S.insert(0);
    } else if( q2 == 0 ){ 
      if( n2 > 1 ) S.insert(0);
      buf[1] = 1LL;
      buf[0] = 0LL;
      S.insert(toHash(buf));

    } else {
      rep(_,n2){
	buf[1] = 1LL;
	buf[0] = 0LL;
	S.insert(toHash(buf));
	for(map<ll,ll>::iterator it = coef.begin(); it != coef.end(); it++ ) {
	  buf[it->first] += it->second;
	  assert( buf[it->first] > 0 );
	}
      }
    }
    return S.size();
  }
};