【考试总结】2022-03-05
小 G 的约数
\(\rm LCM(i,j)|n\) 等价于 \(i,j\) 是 \(n\) 的约数，而第三个条件可以导出我们所求就是约数偏序集合中最长反链长度
直接使用 \(\rm Dilworth\) 定理转化成最小链划分，可以直接使用贪心求解，也就是找到最小元之后扫描没有被覆盖的所有元素，如果是当前链尾的倍数就添加到链里面
证明就是如果划分新链一定不优秀，而不划分新链跟谁都一样
Code Display
const int inf=0x3f3f3f3f3f3f3f3f,N=1e6+10;
int Div[N],cnt,n,num[N],tim[N],m;
int pri[N],pri_cnt;
bool fl[N],vis[N];
inline void get_div(int stp,int x){
if(stp>m) return Div[++cnt]=x,void();
for(int i=0,pw=1;i<=tim[stp];++i) get_div(stp+1,x*pw),pw*=num[stp];
return ;
}
signed main(){
freopen("divisor.in","r",stdin); freopen("divisor.out","w",stdout);
n=1e6;
for(int i=2;i<=n;++i){
if(!fl[i]) pri[++pri_cnt]=i;
for(int j=1;j<=pri_cnt&&pri[j]*i<=n;++j){
fl[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
n=read();
for(int i=1;pri[i]*pri[i]<=n;++i){
if(n%pri[i]==0){
num[++m]=pri[i];
while(n%pri[i]==0) n/=pri[i],tim[m]++;
}
}
if(n>1) num[++m]=n,tim[m]=1;
get_div(1,1);
sort(Div+1,Div+cnt+1);
int ans=0;
for(int i=1;i<=cnt;++i) if(!vis[i]){
int now=Div[i]; vis[i]=1;
for(int j=i+1;j<=cnt;++j) if(!vis[j]&&Div[j]%now==0) vis[j]=1,now=Div[j];
++ans;
}
print(ans);
return 0;
}
小 G 的连通图
取 \(L=\prod\limits_{i\in\{{\rm{prime}}\},i\le n} i\) 那么发现 \(L+1\) 和 \([L,L+n-1]\) 中的其它点都不连通
此时找到一个大于 \(\sqrt n\) 的 \(a\) 满足 \(a\ {\text{is prime}},\exists,(k+1)a+1
推导的步骤就是发现 \(a\) 从 \(L\) 的质因子集合拿走之后 \(L,L+a\) 可能不连通
这时候发现 \(L+(k+1)a+1\) 一定和 \(L+1\) 联通那么拿走 \(ka+1\) 并赋上 \((k-1)a+1\) 这个余数就能实现了
那么我们取 \(L\) 是其它素数的倍数，且 \(L\equiv a-1\mod a,L\equiv (k-1)a+1\mod ka+1\)
至于 \(a>\sqrt n\) 的原因，因为 \(L+a*a\) 可能会产生不连通的情况（注意这里 \(L+ka,k\in[1,a)\) 都可以和 \(L+k(a-1)\) 联通，所以不存在这样子的问题）
没有严谨方法证明对于 \(\forall n,\exists k\) 但是在本题数据范围下取 \(k=2\) 就都能找到了
最后要做的工作就是简单的中国剩余定理，写个高精就行了
注意上面的做法只在 \(n\ge 35\) 的时候奏效，那么较小的部分写个暴力就行了。
我的暴力有点门道的样子，把每个 \(n\) 的方案打印出来看看发现变化的质因子都是一个后缀，同时数量不多，那么可以简单搜索后缀的调整方案就能跑过 \(n\le 200\)
Code Display
const int N=100010;
int n;
struct DSU{
int fa[N];
inline void init(int n){rep(i,1,n) fa[i]=i;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){fa[find(x)]=find(y);}
}T;
inline bool ok(int x){
for(int i=2;i*i<=x;++i) if(x%i==0) return 0;
return 1;
}
bool fl;
int rem[N],pri[N],pri_cnt;
inline bool check(){
T.init(n);
for(int i=1;i<=pri_cnt;++i){
int lst=-1,tmp=rem[i];
for(int j=1;j<=n;++j){
if(tmp==0){
if(~lst) T.merge(lst,j);
lst=j;
}tmp=tmp+1==pri[i]?0:tmp+1;
}
}
int Set=0;
for(int i=1;i<=n;++i) if(T.find(i)==i) ++Set;
return Set==1;
}
const int Bas=100000000;
struct node{
vector a;
inline void adjust(){
int siz=a.size();
for(int i=0;i=Bas){
a.emplace_back(a[siz-1]/Bas);
a[siz-1]%=Bas;
++siz;
}
while(siz>1&&!a[siz-1]) a.pop_back();
return ;
}
node operator +(const node &b)const{
node res;
int s1=a.size(),s2=b.a.size(); res.a.resize(max(s1,s2));
for(int i=0;ipri_cnt){
if(!check()) return ;
fl=1;
return ;
}
for(int i=0;ipri_cnt){
if(!check()) return ;
fl=1;
return ;
}
adj(stp+1);
if(fl) return ;
int lst=rem[stp];
for(int i=0;i 小 G 的 DAG
考虑每 \(\sqrt Q\) 个询问统一回答，那么只对这 \(\sqrt Q\) 个点做其他点到其的可达性统计
每个块里面的覆盖操作可以在结束这个块的回答之后使用 \(\Theta(n)\) 的拓扑排序来维护，当前块的覆盖操作可以暴力
那么在回答这个块里面的询问的时候先找到当前询问的点 \(qx\) 最后一次覆盖操作发生的时间
再对 \(2\) 操作维护 \(Mn_{i,j}\) 表示第 \(j\) 个点在第 \(i\) 个块中的所有 \(2\) 操作取的最小的 \(\min\) 是几，这也可以在每个块结束之后使用拓扑排序维护
那么找到 \(qx\) 最后一次覆盖操作之后本质上就是对 \(2\) 操作的区间求 \(\min\)，使用上面维护的 \(Mn_{i,j}\) 算整块，小块直接暴力扫
Code Display
const int N=1e5+10,inf=0x3f3f3f3f;
bitset<600>to[100010];
int Tim,mark[N],n,m,Q;
vector G[N];
int opt,v;
int in[N],deg[N],id[N];
inline void get_ava(int x){
if(mark[x]==Tim) return ; mark[x]=Tim;
if(id[x]) to[x][id[x]]=1;
for(auto t:G[x]) get_ava(t),to[x]|=to[t];
return ;
}
int typ[N],qu[N],qv[N],block;
int tim[N],val[N],bel[N];
struct node{int p,v,t;};
int Mn[N/300][N];
inline int ask(int x,int L,int R){
assert(id[x]);
int ans=inf;
if(bel[L]>=bel[R]-1){
for(int i=L;i<=R;++i) if(typ[i]==2&&to[qu[i]][id[x]]) ckmin(ans,qv[i]);
}else{
int bed=bel[L]*block,bst=(bel[R]-1)*block+1;
for(int i=L;i<=bed;++i) if(typ[i]==2&&to[qu[i]][id[x]]) ckmin(ans,qv[i]);
for(int i=bst;i<=R;++i) if(typ[i]==2&&to[qu[i]][id[x]]) ckmin(ans,qv[i]);
for(int i=bel[L]+1;i sts;
for(int i=1;i<=n;++i) if(!in[i]) sts.push_back(i);
block=2*sqrt(Q);
for(int i=1;i<=Q;++i){
bel[i]=(i-1)/block+1;
typ[i]=read(),qu[i]=read();
if(typ[i]<=2) qv[i]=read();
}
int qcnt=0;
for(int bb=1;bb<=bel[Q];++bb){
int L=(bb-1)*block+1,R=min(Q,bb*block);
int num=0;
vector nodes;
vector cov;
for(int i=L;i<=R;++i) if(typ[i]==3&&!id[qu[i]]) id[qu[i]]=++num,nodes.push_back(qu[i]);
++Tim;
for(auto t:sts) get_ava(t);
for(int i=L;i<=R;++i){
if(typ[i]==1) cov.push_back({qu[i],qv[i],i});
else if(typ[i]==3){
int lsttim=tim[qu[i]],ans=val[qu[i]];
int siz=cov.size();
for(int j=siz-1;~j;--j) if(to[cov[j].p][id[qu[i]]]){
lsttim=cov[j].t;
ans=cov[j].v;
break;
}
ckmin(ans,ask(qu[i],lsttim+1,i));
print(ans);
}else ckmin(Mn[bb][qu[i]],qv[i]);
}
for(auto t:cov) tim[t.p]=t.t,val[t.p]=t.v;
queue q;
for(int i=1;i<=n;++i){
deg[i]=in[i];
if(!deg[i]) q.push(i);
}
while(q.size()){
int fr=q.front(); q.pop();
for(auto t:G[fr]){
if(tim[fr]>tim[t]) tim[t]=tim[fr],val[t]=val[fr];
ckmin(Mn[bb][t],Mn[bb][fr]);
if(!(--deg[t])) q.push(t);
}
}
for(auto t:nodes) id[t]=0;
rep(i,1,n) to[i].reset();
}
return 0;
}