TopCoder SRM 500 Div2 Hard GeometricProgressions

手抜き解法でもけっこう通ってしまう問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11343

問題

2つの数列がある。
１つ目は初項b1、公比q1、要素数n1の等比数列である。
２つ目は初項b2、公比q2、要素数n2の等比数列である。
両者に含まれるdistinctな整数の数を答えよ。

解法

b1,b2,q1,q2は結構大きいので、まじめに計算することは不可である。

ただし、この問題には手抜き解答がある。
n1、n2はさほど大きくないので、適当な値でmodを取って列挙すれば、そうそう衝突しない。
以下は２種類の値でmodを取ることで衝突を回避している。

自分はたまたま10^9+7と10^9+9を使ったが、本番全く同じ回答もあったようだ。

class GeometricProgressions {
	public:
	int count(int b1, int q1, int n1, int b2, int q2, int n2) {
		ll mo1=1000000007;
		ll mo2=1000000009;
		set<pair<ll,ll> > S;
		
		ll a1=b1,a2=b1,c=q1;
		while(n1--) S.insert(make_pair(a1,a2)), a1=a1*c%mo1,a2=a2*c%mo2;
		a1=a2=b2,c=q2;
		while(n2--) S.insert(make_pair(a1,a2)), a1=a1*c%mo1,a2=a2*c%mo2;
		
		return S.size();
	}
}

ただし、今回はテストケースが甘かっただけで以下のようにmodを取る値がわかっていれば通さないケースも生成できる。
Algorithm Problem Set Analysis > SRM 500

別のちゃんとした解法はb1,q1,b2,q2を素因数分解することである。
等比数列の各要素を素因数分解の形で表現し、distinctなものを数える。
初項や公比に0や1があるので注意。

class GeometricProgressions {
	public:
	
	vector<ll> enumdiv(ll n) {
		vector<ll> V;
		if(n==1) return vector<ll>(1,1);
		for(ll i=2;i*i<=n;i++) while(n%i==0) V.push_back(i),n/=i;
		if(n>1) V.push_back(n);
		return V;
	}
	
	int count(int b1, int q1, int n1, int b2, int q2, int n2) {
		int i,t,B[2],Q[2],N[2];
		
		B[0]=b1,B[1]=b2;
		Q[0]=q1,Q[1]=q2;
		N[0]=n1,N[1]=n2;
		
		set<vector<pair<int,int> > > S;
		
		FOR(t,2) {
			vector<ll> vb,vq;
			map<int,int> M;
			
			if(B[t]==0) {
				vector<pair<int,int> > V;
				V.push_back(make_pair(0,1));
				S.insert(V);
				continue;
			}
			
			vb=enumdiv(B[t]);
			vq=enumdiv(Q[t]);
			ITR(it,vb) M[*it]++;
			
			FOR(i,N[t]) {
				vector<pair<int,int> > V;
				ITR(it,M) V.push_back(make_pair(it->first,it->second));
				S.insert(V);
				
				if(Q[t]==0 && i<N[t]-1) {
					vector<pair<int,int> > V;
					V.push_back(make_pair(0,1));
					S.insert(V);
					break;
				}
				if(Q[t]==1) continue;
				
				ITR(it,vq) M[*it]++;
			}
		}
		return S.size();
	}
}

まとめ

まじめに解くと結構面倒だけど、手抜き解答は相当楽。