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; }
感想
英文の問題ホント読めない。