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