因为今天省选组也做a组，以为今天a组会很难，就做了做b组。t1和t3强行暴力，好在有t2保底。t1和正解就差一点，然而考试时死活想不起来......
今天改题可以少改一道了！ovo
救救孩子吧！t1T到上天......然后打完后电脑蓝屏了。不想动弹
好吧，重打了一遍，终于调对了。
t1：
质因数分解，然后二分m，找因子个数判断。注意质因数分解的方式......
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int prime[100010],ps[100010],dv[100010],cntt,n,tot; int a[100010],b[100010]; long long cnt[100010]; int check(long long mid) { for(int i=1;i<=tot;i++) { long long con=0; for(long long j=b[i];j<=mid;j*=b[i]) { con=(con+mid/(j)); } if(con<cnt[b[i]]) return 0; } return 1; } int main() { freopen("factorial.in","r",stdin); freopen("factorial.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=100000;i++) prime[i]=1; dv[1]=1; for(int i=2;i<=100000;i++) { if(prime[i]) ps[++cntt]=i,dv[i]=i; for(int j=1;j<=cntt;j++) { if(ps[j]*i>100000) break; prime[ps[j]*i]=0; dv[i*ps[j]]=ps[j]; if(i%ps[j]==0) break; } } for(int i=1;i<=n;i++) { while(dv[a[i]]!=a[i]) { if(!cnt[dv[a[i]]]) b[++tot]=dv[a[i]]; cnt[dv[a[i]]]++; a[i]/=dv[a[i]]; } if(a[i]!=1) { if(!cnt[a[i]]) b[++tot]=a[i]; cnt[a[i]]++; } } long long l=1,r=100000000; while(l<r) { long long mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } cout<<l; fclose(stdin); fclose(stdout); return 0; }
先整上t2吧：
这道题正解是搜索，但我考试时觉得它和day3的t2有点像，就写了一个差不多的套路。向不用拐弯可以到达的点连边，然后一个spfa就出答案了。当时有点虚，但反正愉悦ac了，快乐。