说实话吧,今天算是一般水平
不怎么想写题解......
结论题,直接背包做,还有一个东西,一个数的约数个数是小于根号级别的
#include<bits/stdc++.h> using namespace std; #define int long long #define fo(i,x,y) for(int i=(x);i<=(y);i++) #define fu(i,x,y) for(int i=(x);i>=(y);i--) int read(){ int s=0,t=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();} while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} return s*t; } const int N=105; int n,p[N],q[N],cp; int dp[N][N],ans; signed main(){ freopen("divisor.in","r",stdin); freopen("divisor.out","w",stdout); n=read(); for(int i=2;i*i<=n;i++){ if(n%i==0)p[++cp]=i; while(n%i==0)q[cp]++,n/=i; } if(n!=1)p[++cp]=n,q[cp]=1; dp[0][0]=1;int sum=0; fo(i,1,cp){ fo(j,0,q[i]){ fo(k,0,sum){ dp[i][j+k]+=dp[i-1][k]; } } sum+=q[i]; } fo(i,0,sum)ans=max(ans,dp[cp][i]); printf("%lld",ans); return 0; }
构造题,好nm难
首先让左端点是n以内的质数相乘,发现L+1这个玩意被隔绝了
所以我们拿出一个质数a来,让a整除L+1,于是a就不能整除L了
于是我们发现L+1和L+a+1联通了,但是L+a却与世隔绝了,所以我们让L+a和L+3a+1联通
于是我们再次从L中拿出一个质数2a+1,于是就好了
解个同余方程就完事了......
#include<bits/stdc++.h> using namespace std; #define int long long #define fo(i,x,y) for(int i=(x);i<=(y);i++) #define fu(i,x,y) for(int i=(x);i>=(y);i--) int read(){ int s=0,t=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();} while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} return s*t; } const int N=2e7+5; int n,fa[N]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void merge(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy)fa[fx]=fy; } int p[N],cnt;bool vis[N]; void spj(){ for(int i=1;1.0*clock()/CLOCKS_PER_SEC<=0.8&&i<=1000000;i++){ int l=i,r=i+n-1; fo(j,l,r)fa[j]=j; fo(j,1,cnt){ if(p[j]>=n)break; int las=0,v=p[j]; for(int k=(l-1)/v*v+v;k<=r;k+=v){ if(las)merge(las,k); las=k; } } int now=find(l);bool fl=true; fo(j,l+1,r)if(find(j)!=now){fl=false;break;} if(fl){printf("%lld",l);return ;} } printf("No solution"); } int a,b,ma=1,mb=1; int exgcd(int a,int b,int &x,int &y){ if(!b)return x=1,y=0,a; int g=exgcd(b,a%b,x,y),t=x; x=y;y=t-a/b*y;return g; } struct BIG{ #define bas 100000000 int x[10005]; BIG(){memset(x,0,sizeof(x));} BIG operator * (int a)const{ BIG ret=*this;int ys=0; fo(i,1,x[0]){ ret.x[i]=ret.x[i]*a+ys; ys=ret.x[i]/bas; ret.x[i]%=bas; } while(ys){ ret.x[0]++;ret.x[ret.x[0]]=ys; ys=ret.x[ret.x[0]]/bas; ret.x[ret.x[0]]%=bas; } return ret; } BIG operator + (BIG a)const{ BIG ret;ret.x[0]=max(x[0],a.x[0]); fo(i,1,ret.x[0]){ ret.x[i]+=x[i]+a.x[i]; ret.x[i+1]=ret.x[i]/bas; ret.x[i]%=bas; } while(ret.x[ret.x[0]+1]){ ret.x[0]++; ret.x[ret.x[0]+1]=ret.x[ret.x[0]]/bas; ret.x[ret.x[0]]%=bas; } return ret; } void print(){ printf("%lld",x[x[0]]); fu(i,x[0]-1,1)printf("%08lld",x[i]); printf("\n"); } }ba,bb,ans; signed main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); n=read(); fo(i,2,n){ if(!vis[i])p[++cnt]=i; for(int j=1;j<=cnt&&i*p[j]<=n;j++){ vis[i*p[j]]=true; if(i%p[j]==0)continue; } } if(n<=35)return spj(),0; fo(i,sqrt(n)+1,n)if(!vis[i]&&!vis[2*i+1]){a=i;b=2*i+1;break;} ba.x[0]=ba.x[1]=1;bb.x[0]=bb.x[1]=1; //cerr<<a<<" "<<b<<endl; fo(i,1,cnt){ if(p[i]==a||p[i]==b)continue; ba=ba*p[i];ma=ma*p[i]%a; bb=bb*p[i];mb=mb*p[i]%b; } ba=ba*b;ma=ma*b%a; bb=bb*a;mb=mb*a%b; //ba.print();bb.print(); int x,y; exgcd(ma,a,x,y);x+=((-x/a)+1)*a; ba=ba*x;ba=ba*(a-1); exgcd(mb,b,x,y);x+=((-x/b)+1)*b; bb=bb*x; bb=bb*(a+1); ans=ba+bb; ans.print(); return 0; }
遇事不决想分块!!!
#include<bits/stdc++.h> using namespace std; #define fo(i,x,y) for(int i=(x);i<=(y);i++) #define fu(i,x,y) for(int i=(x);i>=(y);i--) int read(){ int s=0,t=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();} while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} return s*t; } const int N=1e5+5; const int SQ=505; const int inf=0x3f3f3f3f; int n,m,QQ,sq,ans[N],val[N],las[N],bl[N]; struct E{int to,nxt;}e[N]; int head[N],rp; void add_edg(int x,int y){e[++rp].to=y;e[rp].nxt=head[x];head[x]=rp;} struct Q{int tp,x,v;}q[N]; int ys[N],cys; bitset<SQ> bit[N]; bool vibit[N]; void dfs_bit(int x){ if(vibit[x])return ; if(ys[x])bit[x].set(ys[x]); vibit[x]=true; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; if(!vibit[y])dfs_bit(y); bit[x]|=bit[y]; } } void sol_bit(int l,int r){ cys=0;fo(i,l,r)if(q[i].tp==3)ys[q[i].x]=++cys; fo(i,1,n)bit[i].reset(),vibit[i]=false; fo(i,1,n)if(!vibit[i])dfs_bit(i); } void clear_bit(int l,int r){fo(i,l,r)if(q[i].tp==3)ys[q[i].x]=0;} bool canreach(int x,int y){return bit[x][ys[y]];} bool vifir[N]; void dfs_fir(int x,int v,int t){ if(vifir[x])return ; val[x]=v;las[x]=t;vifir[x]=true; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; if(vifir[y])continue; dfs_fir(y,v,t); } } void sol_fir(int l,int r){ // { // fo(nn,l,r)if(q[nn].tp==1){ // fo(i,1,n)vifir[i]=false; // dfs_fir(q[nn].x,q[nn].v,nn); // } // return ; // } fo(i,1,n)vifir[i]=false; fu(i,r,l)if(q[i].tp==1)dfs_fir(q[i].x,q[i].v,i); } int sec[SQ][N]; bool visec[N]; void dfs_sec(int x,int v,int id){ if(visec[x])return ; sec[id][x]=min(sec[id][x],v); visec[x]=true; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; if(visec[y])continue; dfs_sec(y,v,id); } } Q S[N];int cs; bool comS(Q a,Q b){return a.v<b.v;} void sol_sec(int l,int r,int id){ fo(i,1,n)visec[i]=false,sec[id][i]=inf; cs=0;fo(i,l,r)if(q[i].tp==2){ //fo(j,1,n)visec[j]=false; //dfs_sec(q[i].x,q[i].v,id); S[++cs]=q[i]; }//return ; if(cs==0)return ; sort(S+1,S+cs+1,comS); fo(i,1,cs)dfs_sec(S[i].x,S[i].v,id); } int get_sec(int l,int r,int x){ int ret=inf; // { // fo(i,l,r)if(q[i].tp==2&&canreach(q[i].x,x))ret=min(ret,q[i].v); // return ret; // } // fo(i,min(l,bl[l]*sq+1),max(r,(bl[r]-1)*sq))if(q[i].tp==2&&canreach(q[i].x,x))ret=min(ret,q[i].v); fo(i,bl[l]+1,bl[r]-1){ // fo(j,(i-1)*sq+1,i*sq)if(q[j].tp==2&&canreach(q[j].x,x))ret=min(ret,q[j].v); ret=min(ret,sec[i][x]); } fo(i,l,min(bl[l]*sq,r))if(q[i].tp==2&&canreach(q[i].x,x))ret=min(ret,q[i].v); if(bl[l]!=bl[r]){fo(i,max(l,(bl[r]-1)*sq+1),r)if(q[i].tp==2&&canreach(q[i].x,x))ret=min(ret,q[i].v);} //fo(i,l,r)if(q[i].tp==2&&canreach(q[i].x,x))ret=min(ret,q[i].v); return ret; } signed main(){ freopen("dag.in","r",stdin); freopen("dag.out","w",stdout); n=read();m=read();QQ=read();sq=500; fo(i,1,m){ int x=read(),y=read(); add_edg(x,y); } fo(i,1,QQ){ q[i].tp=read();q[i].x=read(); if(q[i].tp!=3)q[i].v=read(); bl[i]=(i-1)/sq+1; } fo(nn,1,bl[QQ]){ int l=(nn-1)*sq+1,r=min(nn*sq,QQ); sol_bit(l,r); fo(i,l,r)if(q[i].tp==3){ ans[i]=val[q[i].x];int ls=las[q[i].x]; fo(j,l,i-1)if(q[j].tp==1&&canreach(q[j].x,q[i].x)){ ans[i]=q[j].v;ls=j; } ans[i]=min(ans[i],get_sec(ls+1,i-1,q[i].x)); } clear_bit(l,r);sol_fir(l,r);sol_sec(l,r,nn); } fo(i,1,QQ)if(q[i].tp==3)printf("%d\n",ans[i]); }