题目链接
题面简述
求([1, n])中约数个数最多的数。
(n le 10^{200})
题解
首先，答案一定是一个反素数。
什么是反素数？
一个正整数(x)是反素数的充要条件是：([1, x - 1])中的整数的约数个数都小于(x)的约数个数。
反素数有什么性质？
把一个反素数分解成(p_1^{a_1}p_2^{a_2}...p_n^{a_n})的形式，则(a_1 ge a_2 ge ... ge a_n)。
除(1)以外，一个反素数(x)一定可以由一个小于(x)的反素数乘上一个质数得来。（证明大概比较显然？感性理解一下 = =）
如果我们能求出(10^{200})以内所有反质数，询问时直接lower_bound即可。
由此设计出算法：
-
维护一个堆，一开始只放(1)进去；
-
每次取堆中最小的数（堆顶元素）；
-
判断这是不是一个反素数：根据定义，如果比它小的反素数中有约数个数与它相等或更多的，则它不是反素数。维护当前已经出堆的反素数的约数个数的最大值，如果当前堆顶元素的约数个数不比它大，则它不是反素数。
-
枚举各个合法的素数（要求满足性质1）和它相乘，如果没有超出(10^{200})则也压到堆中。
这样就能求出(10^{200})以内所有反质数了（实际上只有3810个！）
这道题需要高精度，好在只需要高精度乘低精度即可。
AC代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define space putchar(' ')
#define enter putchar('
')
using namespace std;
typedef long long ll;
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 1000005, maxp = 100;
int T, prime[N], pcnt, tot;
bool np[N];
char s[256];
struct big {
ll n[256], l;
big(){
memset(n, 0, sizeof(n));
n[1] = l = 1;
}
void out(){
for(int i = l; i; i--)
write(n[i]);
}
bool operator < (const big &b) const {
if(l != b.l) return l < b.l;
for(int i = l; i; i--)
if(n[i] != b.n[i]) return n[i] < b.n[i];
return 0;
}
bool operator > (const big &b) const {
if(l != b.l) return l > b.l;
for(int i = l; i; i--)
if(n[i] != b.n[i]) return n[i] > b.n[i];
return 0;
}
big operator * (ll x) const {
big c;
c.l = l;
for(int i = 1; i <= l; i++)
c.n[i] = n[i] * x;
while(x) c.l++, x /= 10;
for(int i = 1; i <= c.l; i++)
c.n[i + 1] += c.n[i] / 10, c.n[i] %= 10;
while(!c.n[c.l]) c.l--;
return c;
}
} MAX, cur;
struct data{
big num;
int cnt[maxp];
data(){
memset(cnt, 0, sizeof(cnt));
}
data(big x){
num = x;
memset(cnt, 0, sizeof(cnt));
}
bool operator < (const data &b) const{
return num > b.num;
}
data operator * (int p) const{
data c;
c.num = num * prime[p];
memcpy(c.cnt, cnt, sizeof(cnt));
c.cnt[p]++;
return c;
}
} lst[4005];
priority_queue <data> que;
void euler(int n){
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;
}
}
}
int main(){
euler(1000000);
MAX.l = 201;
MAX.n[201] = MAX.n[1] = 1;
cur.n[1] = 0;
que.push(data());
while(!que.empty()){
data u = que.top();
que.pop();
big d;
for(int p = 1; u.cnt[p]; p++)
d = d * (u.cnt[p] + 1);
if(!(cur < d)) continue;
lst[++tot] = u;
cur = d;
for(int p = 1; p < maxp && (p == 1 || u.cnt[p - 1]); p++)
if((p == 1 || u.cnt[p] < u.cnt[p - 1])){
data v = u * p;
if(v.num < MAX) que.push(v);
}
}
reverse(lst + 1, lst + tot + 1);
read(T);
while(T--){
scanf("%s", s + 1);
big n;
n.l = strlen(s + 1);
for(int i = 1; i <= n.l; i++)
n.n[n.l - i + 1] = s[i] - '0';
data v = data(n);
data u = *lower_bound(lst + 1, lst + tot + 1, v);
big d;
for(int p = 1; u.cnt[p]; p++)
d = d * (u.cnt[p] + 1);
u.num.out(), space, d.out(), enter;
}
return 0;
}