Codeforces 222 C. Reducing Fractions

問題

分数が次のような形で与えられる。
n個の自然数で分子が与えられる。分子は、それらの数すべての積である。
m個の自然数で分母が与えられる。分母は、それらの数すべての積である。


分数を、通分し、元の形式で出力せよ。
すなわち、
それらの積が分子となるようなnout個の自然数と、
それらの積が分母となるようなmout個の自然数を出力せよ。


ただし、nout, mout≦10^5,
出力する自然数は10^7以下でなくてはならない。
答えが複数ある場合はどれを出力してもかまわない。

制約条件

n, m≦10^5
入力される自然数は10^7以下

方針

元の自然数の列のうち、公約数をもつ部分を公約数で割れるだけ割って出力すれば、
条件を満たす。


それはどうするかと言うと、
分子、分母をそれぞれ素因数分解するのだが、そのときに、
素因数と同時に、素因数が何番目の数から来たかを持つようにする。


この素因数をソートし、尺取で約分していく。
二つの列に公約数があったら、どこから来たかを見て、元の列の数をその公約数で割る。

ソースコード

const int MX = 100000;
int n, m, a[MX], b[MX];
bool p[4000];
vi prime;

int main(){
	
	for(int i = 2; i * i < 4000; i++) if(!p[i]) for(int j = i * i; j < 4000; j += i) p[j] = 1;
	for(int i = 2; i < 4000; i++) if(!p[i]) prime.pb(i);
	
	scanf("%d%d", &n, &m);
	vector<pi> A, B;
	
	rep(i, n){
		scanf("%d", a + i);
		int k = a[i];
		for(int j = 0; j < prime.size() && prime[j] * prime[j] <= k; j++)
		while(k % prime[j] == 0) A.pb(mp(prime[j], i)), k /= prime[j];
		
		if(k > 1) A.pb(mp(k, i));
	}
	rep(i, m){
		scanf("%d", b + i);
		int k = b[i];
		for(int j = 0; j < prime.size() && prime[j] * prime[j] <= k; j++)
		while(k % prime[j] == 0) B.pb(mp(prime[j], i)), k /= prime[j];
		
		if(k > 1) B.pb(mp(k, i));
	}
	
	sort(all(A));
	sort(all(B));
	
	int k = 0;
	rep(i, A.size()){
		while(k < B.size() && B[k].first < A[i].first) k++;
		if(k < B.size() && A[i].first == B[k].first){
			a[A[i].second] /= A[i].first;
			b[B[k].second] /= A[i].first;
			k++;
		}
	}
	
	cout << n << " " << m << endl;
	rep(i, n) cout << a[i] << (i == n - 1 ? "\n" : " ");
	rep(i, m) cout << b[i] << (i == m - 1 ? "\n" : " ");
	
	return 0;
}