Codeforces Round #137 (Div. 2) C : Reducing Fractions

問題概要

長さN(<10^5)の数列Aと長さM(<10^5)の数列Bが与えられる(A[i], B[i] < 10^7)。(Aの積)/(Bの積)と等しくなるような長さ10^5以下、要素10^7以下の数列X,YでXの積とYの積が互いに素であるようなものを出力する問題。

解法

A,Bの各要素をそれぞれ素因数分解してどちらに分配するか求める。このとき、適当に分配すると長さ10^5以下などを満たさなくなる可能性があるので、元の数列を修正するような形で行う。素因数分解は素数表を作っておいて高速に行う。

修正したコード

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = int(1e5);
const int MAX_P = int(1e7);

int N, M;
int expCount[MAX_P + 1];
int as[MAX_N], bs[MAX_N], ts[MAX_N];

const int MAX_SEIVE = MAX_P;
int primeFactor[MAX_SEIVE + 1];

void buildPrimeFactorTable() {
	for (int i = 0; i <= MAX_SEIVE; ++i) {
		primeFactor[i] = i;
	}
	for (int i = 2; i*i <= MAX_SEIVE; i++) if (primeFactor[i] == i) {
		for (int j = i<<1; j <= MAX_SEIVE; j += i) {
			primeFactor[j] = i; 
		}
	}
}

void init() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
	for (int i = 0; i < M; ++i) {
		scanf("%d", bs + i);
	}
}

void factorize(int xs[], int len, int add) {
	memcpy(ts, xs, sizeof(ts));
	for (int i = 0; i < len; ++i) {
		for (int p ; ts[i] != 1; ts[i] /= p) {
			p = primeFactor[ts[i]];
			expCount[p] += add;
		}
	}
}

void construct(int xs[], int len) {
	fill(ts, ts + len, 1);
	for (int i = 0; i < len; ++i) {
		for (int p ; xs[i] != 1; xs[i] /= p) {
			p = primeFactor[xs[i]];
			if (expCount[p] > 0) {
				--expCount[p];
				ts[i] *= p;
			}
		}
	}

	memcpy(xs, ts, sizeof(ts));
}

void solve() {
	factorize(as, N, 1);
	factorize(bs, M, -1);

	construct(as, N);
	for (int i = 0; i <= MAX_P; ++i) {
		expCount[i] *= -1;
	}
	construct(bs, M);

	printf("%d %d\n", N, M);
	for (int i = 0; i < N; ++i) {
		printf("%d%c", as[i], i==N-1 ? '\n' : ' ');
	}
	for (int i = 0; i < M; ++i) {
		printf("%d%c", bs[i], i==M-1 ? '\n' : ' ');
	}
}

int main() {
	buildPrimeFactorTable();
	init();
	solve();
	return 0;
}