hdu2521

maksyuki 发表于 oj 分类，标签: 数论-筛法

15 9月 2015

反素数

Problem Description

反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。

Input

第一行输入n,接下来n行测试数据
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].

Output

输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数.

Sample Input

2 3

1 10

47 359

Sample Output

240

Hint 2的因子为：1 210的因子为:1 2 5 10

Source

HDU 2008-10 Programming Contest

题目类型：因子个数

算法分析：由于数据比较小，可以先打表然后直接查询得到最大值时的答案

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1000000000 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000 + 66;

long long GetFactorNum (long long val)
{
    long long tot = 1;
    for (long long i = 2; i * i <= val; i++)
    {
        if (val % i == 0)
        {
            long long temp = 0;
            do
            {
                val /= i;
                temp++;
            } while (val % i == 0);

            tot = tot * (temp + 1);
        }
    }

    if (val > 1)
        tot *= 2;

return tot;
}


long long ans[maxn];

int main()
{
//    ifstream cin("aaa.txt");

    for (long long i = 1; i <= 5000 + 4; i++)
        ans[i] = GetFactorNum (i);

    int t;
    cin >> t;

    while (t--)
    {
        int a, b;
        cin >> a >> b;

        int maxval = -INF, tot = -1;
        for (int i = a; i <=b; i++)
        {
            if (maxval < ans[i])
            {
                maxval = ans[i];
                tot = i;
            }
        }

        cout << tot <<endl;
    }
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1000000000 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000 + 66;

long long GetFactorNum (long long val)

{

long long tot = 1;

for (long long i = 2; i * i <= val; i++)

{

if (val % i == 0)

{

long long temp = 0;

{

val /= i;

temp++;

} while (val % i == 0);

tot = tot * (temp + 1);

}

if (val > 1)

tot *= 2;

return tot;

}

long long ans[maxn];

int main()

{

// ifstream cin("aaa.txt");

for (long long i = 1; i <= 5000 + 4; i++)

ans[i] = GetFactorNum (i);

int t;

cin >> t;

while (t--)

{

int a, b;

cin >> a >> b;

int maxval = -INF, tot = -1;

for (int i = a; i <=b; i++)

{

if (maxval < ans[i])

{

maxval = ans[i];

tot = i;

}

cout << tot <<endl;

}

return 0;

}

hdu2222

hdu2594

一	二	三	四	五	六	日
« 6月
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

超客的水墨烟雨

hdu2521

反素数

分类目录

标签云

书签

近期评论