反素数
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
3
2 3
1 10
47 359
Sample Output
2
6
240
Hint 2的因子为:1 210的因子为:1 2 5 10
Source
HDU 2008-10 Programming Contest
题目类型:因子个数
算法分析:由于数据比较小,可以先打表然后直接查询得到最大值时的答案
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#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; } |
- « 上一篇:hdu2222
- hdu2594:下一篇 »