刚开始认为所有因数都得选,丢给gpt写了一个因数覆盖然后选全部被覆盖到的质数的程序,交上去WA了才发现自己读假题了.
答案取log要最小,那么选大数和选小数没有特别大的区别,但是你要尽量少的选数.
首先把所有本来就是质数的选了.
然后剩下的合数先分解一轮质因数,如果有命中的质数那就不管了,不然我们堆起来另作考虑.
本来想状压dp的,但是1e6内剩下的质数大概有1000个?反正很大.
但是这个题数据可以理解为随机的,那么冲一发贪心.
然后过了,离谱.
具体地,我们定义”一轮”为,选一个前面没选过的数字.
把当前剩下的没满足的数字都过一遍,还有没满足的数字的统计剩下的质数哪个出现次数最多.(相同出现次数显然选较小那个)
然后贪心选这个,继续下一轮.
Flu懒得写这个一轮一轮的脚本,手修的,代码非常丑陋: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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace fastio{
const int bufl=1<<20;
const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
struct IN{
FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
IN& operator>>(char &a){a=getChar();while(a<=32)a=getChar();return *this;}
IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
IN& operator>>(string &a){a.clear();char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
IN& operator>>(int &a){getInt(a);return *this;}
IN& operator>>(long long &a){getInt(a);return *this;}
IN& operator>>(__int128 &a){getInt(a);return *this;}
IN& operator>>(float &a){getDouble(a);return *this;}
IN& operator>>(double &a){getDouble(a);return *this;}
IN& operator>>(long double &a){getDouble(a);return *this;}
};
struct OUT{
FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
OUT(){IT=stdout,Eps=6,Acc=0.5;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=0.5;}
inline void ChangEps(int x=6){Eps=x;}
inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
inline void putChar(int a){*os++=a;if(os==ot)flush();}
template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 ff=(a-(__int128)a)*base2[Eps+2],gg=0;ff+=50;while(ff>0){ff/=10;gg++;}__int128 b=a;if(gg==Eps+3){putInt(b+1);}else{putInt(b);}a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
OUT& operator<<(char a){putChar(a);return *this;}
OUT& operator<<(const char *a){while(*a)putChar(*a++);return *this;}
OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
OUT& operator<<(int a){putInt(a);return *this;}
OUT& operator<<(long long a){putInt(a);return *this;}
OUT& operator<<(__int128 a){putInt(a);return *this;}
OUT& operator<<(unsigned int a){putInt(a);return *this;}
OUT& operator<<(unsigned long long a){putInt(a);return *this;}
OUT& operator<<(unsigned __int128 a){putInt(a);return *this;}
OUT& operator<<(float a){putDouble(a);return *this;}
OUT& operator<<(double a){putDouble(a);return *this;}
OUT& operator<<(long double a){putDouble(a);return *this;}
~OUT(){flush();}
};
}
fastio::IN fin;
fastio::OUT fout;
int vis[1000010];//存最小质因数,负的表示质数表中的位置(负的)
int p[100010],ptop=0;//存质数
short mu[1000010];//莫比乌斯函数
int musu[1000010];//梅滕斯函数,莫比乌斯前缀和
int phi[1000010];//欧拉函数
long long phisu[1000010];//欧拉函数前缀和
int d[1000010];//存每个数的约数个数
int mnnum[1000010];//最小质因子出现次数
void sieve(int n){//[1,n]
phi[1]=1;phisu[1]=1;mu[1]=1;musu[1]=1;d[1]=1;
int tmp;
for(int i=2;i<=n;++i){
if(!vis[i]){
vis[i]=-(++ptop);
p[ptop]=i;
mu[i]=-1;//
phi[i]=i-1;//
d[i]=2;//
mnnum[i]=1;//
}
for(int j=1;j<=ptop&&i*p[j]<=n;++j){
vis[i*p[j]]=p[j];
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];//
mnnum[i*p[j]]=mnnum[i]+1;//
d[i*p[j]]=d[i]/mnnum[i*p[j]]*(mnnum[i*p[j]]+1);//
break;
}else{
mu[i*p[j]]=-mu[i];//
phi[i*p[j]]=phi[i]*(p[j]-1);//
mnnum[i*p[j]]=1;//
d[i*p[j]]=d[i]*2;//
}
}
musu[i]=musu[i-1]+mu[i];//
phisu[i]=phisu[i-1]+phi[i];//
}
}
int df[1000010];
vector<int>vc1,vc2;
vector<int>fac(int x){
vector<int>res;
while(1){
if(vis[x]<0){
res.push_back(p[-vis[x]]);
break;
}else{
res.push_back(vis[x]);
x/=vis[x];
}
}
return res;
}
vector<int>ffac(int x){
vector<int>res;
auto tmp=fac(x);
unordered_map<int,int>mp;
for(auto i:tmp){
if(mp[i]==0){
mp[i]=1;
res.push_back(i);
}
}
return res;
}
long long n,m,res;
//#define NaraFluorine
int main(){
fin>>n;
fout.ChangEps(10);
sieve(n);
for(int i=3;i<=n;i+=10){
int tmp=i;
if(vis[tmp]<0){
df[tmp]=1;
}else{
vc1.push_back(tmp);
}
}
df[7]=1;
df[17]=1;
df[19]=1;
df[29]=1;
df[37]=1;
df[47]=1;
df[59]=1;
df[67]=1;
df[79]=1;
df[89]=1;
df[97]=1;
df[109]=1;
df[107]=1;
df[127]=1;
df[139]=1;
df[137]=1;
df[149]=1;
df[157]=1;
df[167]=1;
df[179]=1;
df[197]=1;
df[199]=1;
df[229]=1;
df[227]=1;
df[239]=1;
df[269]=1;
df[257]=1;
df[277]=1;
df[307]=1;
df[317]=1;
df[337]=1;
df[349]=1;
df[347]=1;
df[359]=1;
df[367]=1;
df[379]=1;
df[389]=1;
df[409]=1;
df[397]=1;
df[419]=1;
df[439]=1;
df[449]=1;
df[479]=1;
df[457]=1;
df[467]=1;
df[499]=1;
df[487]=1;
df[509]=1;
df[569]=1;
df[547]=1;
df[557]=1;
df[577]=1;
df[587]=1;
df[599]=1;
df[607]=1;
df[617]=1;
df[619]=1;
df[647]=1;
df[659]=1;
df[677]=1;
df[709]=1;
df[719]=1;
df[739]=1;
df[769]=1;
df[727]=1;
df[757]=1;
df[809]=1;
df[829]=1;
df[839]=1;
df[859]=1;
df[919]=1;
df[929]=1;
df[1009]=1;
df[1019]=1;
df[1039]=1;
df[1049]=1;
df[1069]=1;
df[1109]=1;
df[1129]=1;
df[787]=1;
df[797]=1;
for(auto i:vc1){
vector<int>op;
int tmp=i;
while(1){
if(vis[tmp]<0){
op.push_back(p[-vis[tmp]]);
break;
}else{
op.push_back(vis[tmp]);
tmp/=vis[tmp];
}
}
int ff=0;
for(auto j:op){
if(df[j]==1){
ff=1;
break;
}
}
if(ff==0){
vc2.push_back(i);
}
}
fout<<vc2.size();enter;
vector<int>vc3;
for(auto i:vc2){
int tmp=i;
while(1){
if(vis[tmp]<0){
vc3.push_back(p[-vis[tmp]]);
break;
}else{
vc3.push_back(vis[tmp]);
tmp/=vis[tmp];
}
}
}
unordered_map<int,int>mp;
for(auto j:vc3){
// fout<<j;space;
mp[j]++;
}
vector<pair<int,int>>resv;
for(auto i:mp){
resv.push_back({i.second,i.first});
// fout<<i.first<<":"<<i.second;enter;
}
sort(resv.rbegin(),resv.rend());
for(auto i:resv){
fout<<i.second<<":"<<i.first;enter;
}
// sort(vc3.begin(),vc3.end());
// int mm=unique(vc3.begin(),vc3.end())-vc3.begin();
// fout<<mm;
// for(auto j:vc2){
// fout<<j;enter;
// }
long double rres=0;
for(int i=2;i<=n;++i){
if(df[i]){
rres+=log((long double)i);
}
}
fout<<rres;
return 0;
}