51nod 1061 最复杂的数V2

51nod 1061 最复杂的数V2

题目大意：

把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。
例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。
即求 n 以内最大的反素数。

数据范围： n\le 10^{200}, T\le 1000

分析：

1是第一个反素数；维护一个小根堆，每次取堆顶元素，如果其因子个数要大于全部已知反素数，则其也为反素数；我们将这个反素数能扩展出来的所有数（满足反素数性质）加入堆中。

#include <bits/stdc++.h>
using namespace std;

// 此处略去高精度模版
// bigint为高精度的类别名，用到高精度乘long long

typedef pair<bigint, bigint> pll;
#define mp make_pair
const int N = 1e6 + 50;
bigint MAXN, INF;

int prime[N], np[N], pcnt;
void euler() {
    np[0] = np[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!np[i]) {
            prime[++pcnt] = i;
        }
        for(int j = 1; j <= pcnt && i * prime[j] < N; j++) {
            np[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

struct Data {
    bigint num;
    int cnt[105];
    Data() {
        num = 1;
        memset(cnt, 0, sizeof(cnt));
    }
    bool operator > (const Data &a) const {
        return num > a.num;
    }
    Data operator * (int p) const {
        Data ret = *this;
        ret.num = ret.num * prime[p];
        ret.cnt[p]++;
        return ret;
    }
};

bigint cal(Data d)
{
    bigint ret = 1;
    for(int p = 1; d.cnt[p] && p <= pcnt; p++) ret = ret * (d.cnt[p] + 1);
    return ret;
}

priority_queue< Data, vector<Data>, greater<Data> > q;
vector<pll> ls;
void init() {
    bigint cur = 0;
    q.push(Data());
    while(!q.empty()) {
        Data u = q.top(); q.pop();
        bigint d = cal(u);
        if(d <= cur) {
            continue;
        }
        cur = d;
        ls.push_back(mp(u.num, d));
        for(int p = 1; p <= pcnt && (p == 1 || u.cnt[p - 1]); p++) {
            if(p == 1 || u.cnt[p] < u.cnt[p - 1]) {
                Data tmp = u * p;
                if(tmp.num < MAXN) q.push(tmp);
            }
        }
    }
}

int main() {
    euler();
    INF = MAXN = fpow(10, 201);
    init();
    int T; scanf("%d", &T);
    while(T--) {
        bigint n;
        cin >> n;
        pll ans = *(--upper_bound(ls.begin(), ls.end(), mp(n, INF)));
        cout << ans.first << " " << ans.second << endl;
    }
    return 0;
}