省选模拟26
A. 小 G 的约数
将给定的 \(n\) 分解质因数
按照每个因数含有的质因子次数和分类
答案就是最大的哪个
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,ans;
int c[100010],cnt;
int f[100010],siz;
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("divisor.in","r",stdin);
freopen("divisor.out","w",stdout);
n=read();
for(int i=2;i*i<=n;i++) if(n%i==0){cnt++;while(n%i==0) c[cnt]++,n/=i;}if(n!=1) c[++cnt]=1;
sort(c+1,c+1+cnt);f[0]=1;
for(int i=1;i<=cnt;i++){
for(int j=siz;~j;j--) for(int k=c[i];k;k--) f[j+k]+=f[j];
siz+=c[i];
}
for(int i=1;i<=siz;i++) ans=max(ans,f[i]);
printf("%lld\n",ans);
return 0;
}
B. 小 G 的连通图
范围小的可以暴力
范围大的时候考虑构造一种方案
令 \(L=\prod_{i=1,i\ isprime}^{n}i\)
那么他与除了 \(L+1\) 的所有数都相连
调整这种方法使得 \(L+1\) 也被连入集合
找一个 \(a\) 使得 \(L+1\) 与 \(L+a+1\) 相连
但这个时候 \(L\) 就不与 \(L+a\) 相连了
于是考虑再找一个 \(2a+1\)
这样 \(l+a\) 就与 \(l+3a+1\) 相连，同时 \(l+1+a\) 也相连了
同时 \(L\) 还和 \(L+3a+1\) 连在一起，所以就都连在一起了
为了方便构造于是要求 \(a\) 和 \(2a+1\) 都是质数
最后得出 \(L\%a=a-1\) ， \(L\%(2a+1)=a+1\) 且 \(L\) 为其他质数的倍数
\(CRT\) 合并一下就行，暴力枚举倍数也可以
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define B 100000000
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,A,mod,res,t,mu;
int a[100010],len;
int prime[100010],cnt;
int ans[18]={2184,27829,27828,87890,87890,171054,171054,323510,127374,323510,151062,
151062,151062,151061,151060,151059,151058,7106718};
bool is[100010];
inline void mul(int x){
for(int i=1;i<=len;i++) a[i]*=x;
for(int i=1;i<=len;i++) if(a[i]>=B){
a[i+1]+=a[i]/B;a[i]%=B;
if(i==len) len++;
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
n=read();a[1]=1,len=1;
for(int i=2;i<=n;i++){
if(!is[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
is[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
if(n<=16) puts("No solution"),exit(0);
if(n<=35) printf("%lld\n",ans[n-17]),exit(0);
for(int i=sqrt(n);i<=n;i++) if(i*i>n){
if(!is[i]&&!is[2*i+1]){A=i;break;}
}
mod=2*A*A+A,res=1;
for(int i=1;i<=cnt;i++) if(prime[i]!=A&&prime[i]!=2*A+1) mul(prime[i]),res=res*prime[i]%mod;
for(t=res,mu=1;t!=mod-3*A-1;t=(t+res)%mod,mu++);
mul(mu);printf("%lld",a[len]);for(int i=len-1;i;i--) printf("%08lld",a[i]);
return 0;
}
C. 小 G 的 DAG
动态维护不好搞于是根号分治一下
对于 \(1\) 操作，每根号次就更新一次
对于 \(2\) 操作，发现查询时只和上一次 \(1\) 操作后的值有关系
于是可以根号预处理一下，预处理操作完每个块之后的最小值
那么对于剩下的散块直接暴力查询
还剩下一个问题就是如何处理 \(x\) 能否到达 \(y\)
直接 \(bitset\) 开不下，于是可以每根号次操作处理一次，处理所有点能否到这根号次询问的点
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int B=500;
int n,m,Q;
int bl[100010],L[100010],R[100010];
int deg[100010],a[100010],p;
int head[100010],ver[100010],to[100010],tot;
int v[100010],lst[100010];
int mn[100010][210],id[100010],t[100010];
bool is[100010];
pairu[100010];
bitset<510>BT[100010];
queueq;
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
struct opt{int op,u,x;}LL[100010];
inline void upd(){for(int i=1,x;i<=n;i++){x=a[i];v[x]=u[x].first;lst[x]=u[x].second;for(int j=head[x];j;j=to[j]){int y=ver[j];if(u[x].second>u[y].second) u[y]=u[x];}}}
inline void topo(){for(int i=1;i<=n;i++) BT[i].reset();for(int i=n,x;i;i--){x=a[i];if(is[x]) BT[x][id[x]]=1;for(int j=head[x];j;j=to[j]){int y=ver[j];BT[x]|=BT[y];}}}
inline void umn(int blo){for(int i=1,x;i<=n;i++){x=a[i];for(int j=head[x];j;j=to[j]){int y=ver[j];v[y]=min(v[y],v[x]);}}for(int i=1;i<=n;i++) mn[i][blo]=v[i];}
inline void pre(){
for(int i=1;i<=bl[Q];i++){
for(int j=1;j<=n;j++) v[j]=inf;
for(int j=L[i];j<=R[i];j++) if(LL[j].op==2){
v[LL[j].u]=min(v[LL[j].u],LL[j].x);
}
umn(i);
}
}
inline int query(int x,int l,int r){
int res=inf;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++) if(LL[i].op==2) if(BT[LL[i].u][id[x]]) res=min(res,LL[i].x);
return res;
}
for(int i=l;i<=R[bl[l]];i++) if(LL[i].op==2) if(BT[LL[i].u][id[x]]) res=min(res,LL[i].x);
for(int i=L[bl[r]];i<=r;i++) if(LL[i].op==2) if(BT[LL[i].u][id[x]]) res=min(res,LL[i].x);
for(int i=bl[l]+1;i<=bl[r]-1;i++) res=min(res,mn[x][i]);
return res;
}
inline int getv(int x,int l,int r){
int res=v[x];
for(int i=l;i<=r;i++) if(LL[i].op==1){if(BT[LL[i].u][id[x]]) res=LL[i].x,lst[x]=i;}
return res;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("dag.in","r",stdin);
freopen("dag.out","w",stdout);
n=read(),m=read(),Q=read();for(int i=1;i<=Q;i++) bl[i]=(i-1)/B+1;
for(int i=1;i<=bl[Q];i++) L[i]=(i-1)*B+1,R[i]=min(i*B,Q);
for(int i=1,x,y;i<=m;i++){x=read(),y=read();add(x,y);deg[y]++;}
for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
while(!q.empty()){
int x=q.front();q.pop();a[++p]=x;
for(int i=head[x];i;i=to[i]){
int y=ver[i];deg[y]--;
if(!deg[y]) q.push(y);
}
}
for(int i=1;i<=Q;i++){LL[i].op=read(),LL[i].u=read();if(LL[i].op!=3) LL[i].x=read();}p=0;
for(int i=L[1];i<=R[1];i++) if(LL[i].op==3) is[LL[i].u]=1,t[id[LL[i].u]=++p]=LL[i].u;
topo();pre();
for(int i=1;i<=n;i++) v[i]=0;
for(int i=1,res;i<=Q;i++){
if(LL[i].op==1) u[LL[i].u]=make_pair(LL[i].x,i);
if(LL[i].op==3){
res=getv(LL[i].u,L[bl[i]],i);
res=min(res,query(LL[i].u,lst[LL[i].u],i));
printf("%lld\n",res);
}
if(i==R[bl[i]]){
for(int j=1;j<=p;j++) is[t[j]]=0;p=0;
for(int j=L[bl[i]+1];j<=R[bl[i]+1];j++) if(LL[j].op==3) is[LL[j].u]=1,t[id[LL[j].u]=++p]=LL[j].u;
topo();upd();
}
}
return 0;
}