HDOJ 1239 Calling Extraterrestrial Intelligence Again

题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1239

搜索的题目。
我感觉这题直接判断是否满足条件就OK了,为何HDOJ的课件上还说用剪枝?谁能告诉我?
先分析:得到:2<= p,q <=10000。 再用筛选法打表求出10000以内的素数, 接着就是搜索遍历了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
__int64 m, a, b, p, q;
__int64 _maxa, _maxb, _max;
 
bool vis[10001];
int prime[5000];
int main()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 2; i <= 100; i++)
        for(int j = i*2; j <= 10000; j += i)
            vis[j] = 1;
    int n=0;
    for(int i=2; i<=10000; ++i)
        if(vis[i] == 0)
            prime[n++] = i;
    bool flag=0;
    while(scanf("%I64d %I64d %I64d", &m, &a, &b) && (a+b+m))
    {
        _max = _maxa = _maxb = 0;
        flag = 0;
        for(int i=n-1; i>=0; --i)
        {
            for(int j=n-1; j>=i; --j)
                if((prime[j]*prime[i] <= m) && (prime[j]*prime[i]>_max) && (double)prime[i]/prime[j]>=((double)a/b))
                {
                    _max = prime[j]*prime[i];
                    _maxa = i;
                    _maxb = j;
                }
        }
        printf("%d %d\n", prime[_maxa], prime[_maxb]);
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注