読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

AOJ 1232 Calling Extraterrestrial Intelligence Again

問題

4より大きく10^5未満の値mと1以上1000以下の整数a,bが与えられる。
素数の組p,qを考える。
pq <= m,a/b <= p/q <= 1という条件を満たすpqの値が最大の組を考える。

解法

あらかじめ素数を用意して置く。
pとqを固定して二重ループ。
与えられた条件に当てはまるp,qの組の中のpqが最大の組を選ぶ。

ソースコード

#include<iostream>
#include<vector>
#define M 100000
using namespace std;
bool prime[M];
void primeInit()
{
	for (int i = 0; i < M; i++)
	{
		prime[i] = false;
	}
}
void p()
{
	prime[2] = true;
	for (int i = 3; i < M; i++)
	{
		bool flag = false;
		for (int j = 2; j * j <= i; j++)
		{
			if (i % j == 0)
			{
				flag = true;
				break;
			}
		}
		if (!flag)prime[i] = true;
	}
}
int main()
{
	int m, a, b;
	primeInit();
	p();
	while (cin >> m >> a >> b && m != 0 || a != 0 || b != 0)
	{
		double ma = 0;
		int mp = 0;
		int mq = 0;
		for (int p = 2; p <= m / 2; p++)
		{
			if (!prime[p])continue;
			for (int q = 2; q <= m / p; q++)
			{
				if (!prime[q])continue;
				if (1.0 * p * q > ma && 1.0 * p * q <= m && (1.0 * p / q) <= 1 && (1.0 * p / q) >= (a * 1.0 / b))
				{
					ma = p * q;
					mp = p;
					mq = q;
				}
			}
		}

		cout << mp << " " << mq << endl;
	}
	return 0;
}

感想

英文の問題ホント読めない。