因为有些逗,所以打算水一些这样的题目。囧rz。
关键算法:
Miller-Rabbin判断素数。http://www.dxmtb.com/blog/miller-rabbin/
Pollard-Rho找出整数的任意一个因子。http://www.dxmtb.com/blog/pollard-rho/
先跟着他讲的写了一遍。太神了。
找因子的时候因为找出来的是任意一个。所以还要继续二分直到找到最小的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int S=30,C=240; typedef long long ll; ll An; ll mul(ll a,ll b,ll c){ ll r; for(r=0;b;a=(a<<1)%c,b>>=1) if(b&1) r=(r+a)%c; return r; }ll pow(ll a,ll b,ll c){ ll r; for(r=1;b;a=mul(a,a,c),b>>=1) if(b&1) r=mul(r,a,c); return r; }int miller_rabbin(ll n){ if(n==2) return 1; if(n<2||!(n&1)) return 0; int t=0; ll a,x,y,u=n-1; while(!(u&1)) t++, u>>=1; for(int i=0;i<S;i++){ a=rand()%(n-1)+1; x=pow(a,u,n); for(int j=0;j<t;j++){ y=mul(x,x,n); if(y==1&&x!=1&&x!=n-1) return 0; x=y; }if(x!=1) return 0; }return 1; }ll gcd(ll a,ll b){ return (!b)?a:gcd(b,a%b); }ll pollard_rho(ll n,ll c){ ll x,y,d,i=1,k=2; x=rand()%(n-1)+1;y=x; while(++i){ x=(mul(x,x,n)+c)%n; d=gcd(y-x,n); if(1<d&&d<n) return d; if(x==y) return n; if(i==k) y=x,k<<=1; } }void find(ll n,ll c){ ll m; if(n==1) return; if(miller_rabbin(n)){ An=min(An,n); return;} m=n; while(m==n) m=pollard_rho(n,c--); find(m,c); find(n/m,c); }int main(){ int tc; scanf("%d",&tc); ll n; while(tc--){ scanf("%lld",&n); if(miller_rabbin(n)) printf("Prime\n"); else{ An=1ll<<60ll; find(n,1LL*C); printf("%lld\n",An);} }return 0; }
拿SAM来求字符串的最小表示很煞笔吧、好吧、只是拿来练习SAM用的、
把字符串自复制一遍、然后建SAM、然后从root开始跑,每次都跑最小编号的结点,在上面跑|S|个结点。然后输出当前结点的信息就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct SAMNode{ int ch[26],fa,len; inline void init(){ fa=-1; len=0; memset(ch,0xff,sizeof(ch)); } }T[50010]; char s[10010]; int tot,last; void add(int c){ int end=++tot; T[end].init(); int tmp=last; T[end].len=T[last].len+1; while(tmp!=-1 && T[tmp].ch[c]==-1){ T[tmp].ch[c]=end; tmp=T[tmp].fa; }if(!~tmp) T[end].fa=0; else{ int next=T[tmp].ch[c]; if(T[tmp].len+1==T[next].len) T[end].fa=next; else{ int np=++tot; T[np].init(); T[np]=T[next]; T[np].len=T[tmp].len+1; T[end].fa=T[next].fa=np; while(tmp!=-1 && T[tmp].ch[c]==next){ T[tmp].ch[c]=np; tmp=T[tmp].fa; } } }last=end; }int main(){ int tc; scanf("%d",&tc); while(tc--){ tot=0; last=0; T[0].init(); scanf("%s",s); int n=strlen(s); for(int i=0;i<n;i++) add(s[i]-'a'); for(int i=0;i<n;i++) add(s[i]-'a'); int o=0; for(int i=0;i<n;i++) for(int j=0;j<26;j++) if(~T[o].ch[j]){ o=T[o].ch[j]; break; }printf("%d\n",T[o].len-n+1); }return 0; }
理论知识看了好久的说、这里就不写了、
主要的是定义low[u]表示从u或u的子孙出发通过回边可以到达的最低深度优先数dfn[]。
low[u]=min{dfn[u], min{low[w]|w是u的子女}, min{dfn[v]|v与u邻接,且(u,v)是一条回边} }
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; int low[2010],dfn[2010],ss[1010],v[1010],p[2010],n1[2010],h[1010],n,e=0,tot=0; inline void ae(int a,int b){ p[e]=b; n1[e]=h[a]; h[a]=e++;} void dfs(int u){ for(int i=h[u];~i;i=n1[i]) if(!v[p[i]]){ v[p[i]]=1; dfn[p[i]]=low[p[i]]=++tot; dfs(p[i]); low[u]=min(low[u],low[p[i]]); if(low[p[i]]>=dfn[u]) ss[u]++; }else low[u]=min(low[u],dfn[p[i]]); }inline void init(){ memset(h,-1,sizeof(h)); memset(v,0,sizeof(v)); memset(ss,0,sizeof(ss)); e=0;tot=dfn[1]=low[1]=v[1]=1; }int main(){ int u,v,Tc=0; while(scanf("%d",&u),u){ init(); scanf("%d",&v); ae(u,v); ae(v,u); n=max(u,v); while(scanf("%d",&u),u){ scanf("%d",&v); n=max(n,max(u,v)); ae(u,v); ae(v,u); }dfs(1); if(Tc) printf("\n"); printf("Network #%d\n",++Tc); int f=0; if(ss[1]>=1) ss[1]--; for(int i=1;i<=n;i++) if(ss[i]){ f=1; printf(" SPF node %d leaves %d subnets\n",i,ss[i]+1); }if(!f) printf(" No SPF nodes\n"); }return 0; }