题解
我是榜上最后一名= =
可能高精度用vector太慢了吧……什么破题= =
这道题很简单，如果高精度熟练代码……也很简单……然而，参数调了好久
我们发现质数的指数一定是，质数越小，指数越大，这个很显然我不说了
所以我们就用个优先队列BFS就好，队列按数从小到大排序，每次把队列的数取出来作为下一个我们需要的数（也就是大小递增且约数个数严格递增），删掉队列首比这个数约数个数小的数
然后用这个数再扩展一层质数，注意剪枝吧。。
预处理好后回答询问二分就行
质数大小开到85，搜出来的数的总量3810，在TLE的边缘试探……
vector写高精度是真的很慢……
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <set>
//#define ivorysi
#define eps 1e-8
#define mo 974711
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define MAXN 100005
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
const int64 MOD = 1000000007;
const int BASE = 100000000,LEN = 8;
struct Bignum {
vector<int> v;
Bignum(int64 x = 0){
*this = x;
}
Bignum operator = (int64 x) {
v.clear();
do {
v.pb(x % BASE);
x /= BASE;
}while(x);
return *this;
}
Bignum operator = (const string &str) {
int x;
v.clear();
for(int i = str.length() ; i > 0 ; i -= LEN) {
int ed = i,st = max(i - LEN,0);
sscanf(str.substr(st,ed - st).c_str(),"%d",&x);
v.pb(x);
}
return *this;
}
friend Bignum operator * (const Bignum &a,const Bignum &b) {
Bignum c;c.v.clear();
for(int i = 1 ; i <= a.v.size() + b.v.size() ; ++i) c.v.pb(0);
for(int i = 0 ; i < a.v.size() ; ++i) {
int g = 0;
for(int j = 0 ; j < b.v.size() ; ++j) {
int64 x = 1LL * a.v[i] * b.v[j] + c.v[i + j] + g;
c.v[i + j] = x % BASE;
g = x / BASE;
}
int t = i + b.v.size();
while(g) {
int64 x = c.v[t] + g;
c.v[t] = x % BASE;
g = x / BASE;
++t;
}
}
for(int i = c.v.size() - 1 ; i > 0 ; --i) {
if(c.v[i] == 0) c.v.pop_back();
else break;
}
return c;
}
friend Bignum operator / (const Bignum &a,const int x) {
Bignum c;c.v.clear();
for(int i = 1 ; i <= a.v.size() ; ++i) c.v.pb(0);
int g = 0;
for(int i = a.v.size() - 1 ; i >= 0 ; --i) {
int64 y = 1LL * g * BASE + a.v[i];
c.v[i] = y / x;
g = y % x;
}
for(int i = c.v.size() - 1 ; i > 0 ; --i) {
if(c.v[i] == 0) c.v.pop_back();
else break;
}
return c;
}
friend bool operator < (const Bignum &a,const Bignum &b) {
if(a.v.size() < b.v.size()) return true;
else if(a.v.size() > b.v.size()) return false;
else {
for(int i = a.v.size() - 1 ; i >= 0 ; --i) {
if(a.v[i] < b.v[i]) return true;
else if(a.v[i] > b.v[i]) return false;
}
return false;
}
}
friend bool operator == (const Bignum &a,const Bignum &b) {
if(a.v.size() != b.v.size()) return false;
else {
for(int i = a.v.size() - 1 ; i >= 0 ; --i) {
if(a.v[i] != b.v[i]) return false;
}
return true;
}
}
friend bool operator > (const Bignum &a,const Bignum &b) {return b < a;}
friend bool operator != (const Bignum &a,const Bignum &b) {return !(a == b);}
friend bool operator <= (const Bignum &a,const Bignum &b) {return !(a > b);}
friend bool operator >= (const Bignum &a,const Bignum &b) {return !(a < b);}
void print() {
int s = v.size() - 1;
printf("%d",v[s]);
--s;
for(int i = s ; i >= 0 ; --i) {
printf("%08d",v[i]);
}
}
}N;
int T;
bool nonprime[100005];
int prime[100005],cnt;
const int P = 85;
struct node {
Bignum num,val;
int cnt[P + 5];
node(Bignum _num = 0) {
num = _num;
memset(cnt,0,sizeof(cnt));
val = 1;
}
friend node operator * (const node &a,int x) {
node c;c.num = a.num * (Bignum)prime[x];
memcpy(c.cnt,a.cnt,sizeof(c.cnt));
c.cnt[x]++;
c.val = a.val / (a.cnt[x] + 1) * (a.cnt[x] + 2);
return c;
}
friend bool operator < (const node &a,const node &b) {
return a.num < b.num;
}
friend bool operator == (const node &a,const node &b) {
return a.num == b.num;
}
}ans[4005];
int tot = 0;
set<node> S;
void Solve() {
node p = node(1);
int c = 3810;
while(c--) {
ans[++tot] = p;
while(!S.empty()) {
node k = *S.begin();
if(k.val <= p.val) S.erase(S.begin());
else break;
}
S.insert(p * 1);
node k = *S.begin();
S.erase(S.begin());
for(int i = 2 ; i <= cnt ; ++i) {
node t = p * i;
if(t.val <= k.val) continue;
S.insert(t);
}
p = k;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
for(int i = 2 ; i <= 10000 ; ++i) {
if(!nonprime[i]) {
prime[++cnt] = i;
if(cnt >= P) break;
for(int j = 2 ; j <= 10000 / i ; ++j) {
nonprime[i * j] = 1;
}
}
}
ios::sync_with_stdio(false);
Solve();
cin>>T;
string str;
while(T--) {
cin>>str;
N = str;
int L = 1,R = tot;
while(L < R) {
int MID = (L + R + 1) >> 1;
if(ans[MID].num <= N) L = MID;
else R = MID - 1;
}
ans[L].num.print();
putchar(' ');
ans[L].val.print();
putchar('
');
}
return 0;
}