栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 1411 Calling Extraterrest...

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 1411 Calling Extraterrest...

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>using namespace std;#define maxn 100005bool is[maxn];long long prm[maxn];int n, a, b, m, p, q;int getprm(int n){    int i, j, k = 0;    int s, e = (int) (sqrt(0.0 + n) + 1);    memset(is, 1, sizeof(is));    prm[k++] = 2;    is[0] = is[1] = 0;    for (i = 4; i < n; i += 2)        is[i] = 0;    for (i = 3; i < e; i += 2)        if (is[i])        { prm[k++] = i; for (s = i * 2, j = i * i; j < n; j += s)     is[j] = 0;        }    for (; i < n; i += 2)        if (is[i]) prm[k++] = i;    return k;}int binarysearch(){    int l = 0;    int r = n;    while (l < r)    {        int mid = (l + r) / 2 + ((l + r) & 1);        if (((long long)prm[mid]) * prm[mid] <= m) l = mid;        else r = mid - 1;    }    return l;}void work(int l, int r){    int ans = prm[l] * prm[r];    q = p = prm[l];    while (l >= 0)    {        if (prm[l] * b < a * prm[r]) break;        while (r < n - 1 && prm[l] * b >= a * prm[r + 1] && prm[l] * prm[r + 1] <= m) r++;        if (ans < prm[l] * prm[r])        { p = prm[l]; q = prm[r]; ans = prm[l] * prm[r];        }        l--;    }    printf("%d %dn", p, q);}int main(){    n = getprm(maxn - 1);    while (scanf("%d%d%d", &m, &a, &b), m | a | b)    {        int l, r;        l = r = binarysearch();        work(l, r);    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/375225.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号