求比N小的因数最多的数，因数相同时取较小的的。(N<=10^80)
没想法的题目，没想到是搜索。。
首先因子数目 f[i] = ∏(p[i]+1) ,p[i]是所有质因数的个数，这个应该都知道。如果要使因子最多并且数最小，不会用到太大的质数，这个我也不知道怎么证明。。原题解也没有证明。。。
用一个四元组[K,F,N,A[]]表示数K有F个因数，包含N个质因数，每个质因数P[i]分别有A[i]个。然后搜索就可以了，添加一个已有质数A[i]，四元组转化为[K*P[i],F/(A[i]+1)*(A[i]+2),N,A[i]+1]，添加一个新的质数A[i]，四元组转化为，[K*P[i],F*2,N+1,A[i]=1]。
用map存所有的F对应的K，F相同时保留较小的K。
直接做会超时，因为搜索中数是一直递增的，把结果存下来然后离线边搜边更新结果就A了，估计是因为case不多但都是大数据。。。
1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
4 #include <algorithm>
5 #include <map>
6 #include <queue>
7 #include<string>
8 #include<iostream>
9 #define MAXN 200
10 using namespace std;
11 typedef long long LL;
12 const int BMOD = 100000000;
13 const int maxl = (MAXN>>3)+1;
14 struct bign{
15 int s[maxl], len;
16 void init(){memset(s, 0, sizeof s); len = 1;}
17 void clean(){while(len > 1 && !s[len-1]) --len;}
18 bign(){init();}
19 bign(int num){*this = num;}
20 bign(const char *num){*this = num;}
21 bign operator = (int num) {
22 char s[maxl];
23 sprintf(s, "%d", num);
24 return *this = s;
25 }
26 bign operator = (const char *buf) {
27 init();
28 int l = strlen(buf);
29 for(int i = 0, j = l - 1; i < l; ++ i, -- j)
30 s[j >> 3] = s[j >> 3] * 10 + buf[i] - '0';
31 len = (l >> 3) + 1;
32 clean();
33 return *this;
34 }
35 bign operator + (const bign b) {
36 bign c; c.len = 0;
37 int g = 0;
38 for (int i = 0; g || i < max(len, b.len); i++) {
39 c.s[c.len] = g;
40 if(i < len)c.s[c.len] += s[i];
41 if(i < b.len)c.s[c.len] +=b.s[i];
42 g = c.s[c.len]/BMOD, c.s[c.len] %= BMOD, c.len++;
43 }
44 return c;
45 }
46 bign operator * (const bign b) {
47 bign c;
48 c.len = len + b.len;
49 LL lin;
50 for (int i = 0; i < len; i++)
51 for (int j = 0; j < b.len; j++){
52 lin = (LL)s[i] * b.s[j] + c.s[i+j];
53 c.s[i+j] = lin % BMOD;
54 c.s[i+j+1] += lin / BMOD;
55 }
56 for (int i = 0; i < c.len - 1; i++) c.s[i+1] += c.s[i] / BMOD, c.s[i] %= BMOD;
57 c.clean();
58 return c;
59 }
60 bool operator <(const bign b) const{
61 if(len != b.len) return len < b.len;
62 for (int i = len - 1; i >= 0; i--)
63 if (s[i] != b.s[i]) return s[i] < b.s[i];
64 return false;
65 }
66 bool operator <=(const bign b) const {return !(b < *this);}
67
68 void print() {
69 for(int i = len - 1; i >= 0; i--) {
70 if (i == len - 1) printf("%d", s[i]);
71 else printf("%08d", s[i]);
72 }
73 }
74 };
75
76 struct stt{
77 bign k;
78 LL f;
79 int n,a[MAXN];
80 stt(){}
81 stt(bign kk, LL ff, int nn) {k = kk, f= ff, n = nn;}
82 };
83
84 struct ans{
85 bign in, res;
86 LL f;
87 };
88 map<LL, bign> mp;
89 vector<ans> vec;
90 bign maxp, pri[MAXN];
91 int prs;
92 //pri[i]和stt里的a[i]是对应的,a[i]是pri[i]的个数
93 void init() {
94 prs = 0;
95 for (int i = 2, j, flag; i < MAXN; i++) {
96 for (flag = 1,j = 2; j < i; j++)
97 if (i % j == 0) flag = 0;
98 if (flag) pri[prs++] = i;
99 }
100 }
101 bool canadd(stt st) {
102 if (maxp < st.k) return false;
103 if (mp.find(st.f) == mp.end() || st.k < mp[st.f]){
104 mp[st.f] = st.k;
105 return true;
106 }
107 return false;
108 }
109 void updateans(stt st) {
110 for (int i = 0; i < vec.size(); i++) {
111 if (st.k <= vec[i].in && (st.f > vec[i].f || st.f == vec[i].f && st.k < vec[i].res))
112 vec[i].res = st.k, vec[i].f = st.f;
113 }
114 }
115 void bfs(){
116 queue<stt> q;
117 mp.clear();
118 mp[1] = 1;
119 q.push(stt(1, 1, 0));
120 while (!q.empty()) {
121 stt ost = q.front(); q.pop();
122 updateans(ost);
123 //添加已有质数
124 for (int i = 0 ; i < ost.n; i++) {
125 stt nst = ost;
126 nst.k = ost.k * pri[i];
127 nst.f = ost.f / (ost.a[i]+1) * (ost.a[i]+2);
128 nst.a[i]++;
129 if (canadd(nst)) q.push(nst);
130 }
131 //添加还未添加的质数
132 stt nst = ost;
133 nst.k = ost.k * pri[ost.n];
134 nst.f = ost.f * 2;
135 nst.a[nst.n++] = 1;
136 if (canadd(nst)) q.push(nst);
137 }
138 }
139 char s[MAXN];
140 int main() {
141 //freopen("test.in","r",stdin);
142 init();
143 maxp = 0;
144 vec.clear();
145 mp.clear();
146 while (scanf("%s", s) != EOF) {
147 ans a; a.in = s, a.res = 1, a.f = 1;
148 if (maxp < a.in) maxp = a.in;
149 vec.push_back(a);
150 }
151 bfs();
152 for (int i = 0; i < vec.size(); i++)
153 vec[i].res.print(), printf(" %I64d\n",vec[i].f);
154 return 0;
155 }