DZY 's BLOG

关键算法：

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;
}