Codeforces Round #132 (Div. 2) A : Bicycle Chain

問題概要

長さN,M(<50)の配列A,Bが与えられる。argmin_{i,j, B[j]%A[i]==0} B[j]/A[i] の濃度を求める問題。

解法

全探索。

acceptされたコード

#include <cstdio>
using namespace std;

template<typename numType>
inline bool updateMax(numType& old, const numType& test) {
	if (old < test) {
		old = test;
		return true;
	}
	return false;
}

const int MAX_N = 50;

int N, M;
int as[MAX_N], bs[MAX_N];

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

int solve() {
	int maxi = -1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (bs[j] % as[i] == 0) {
				updateMax(maxi, bs[j] / as[i]);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (bs[j] % as[i] == 0 && bs[j] / as[i] == maxi) {
				++ans;
			}
		}
	}
	return ans;
}

int main() {
	init();
	printf("%d\n", solve());

	return 0;
}