Template.-白红宇

Template.

阅读量：6415 次

发布时间：2019-06-23

本文共 21066 字，大约阅读时间需要 70 分钟。

Background

还有一个礼拜就省选了，连板子都不会打的Zars19觉得应该来一次模板补全计划。

（尽管好多该学的东西还没学）

Update:省选已经完了…但是还没补全

树

1.0 树链剖分（BZOJ1036 [ZJOI2008]树的统计Count）

#include
      
       #include
       
        #include
        
         #include
         
          #define INF 0x3f3f3f3f#define MAXN 30005using namespace std;int n,q,sz=0,head[MAXN],w[MAXN],ans;int dep[MAXN],top[MAXN],pos[MAXN],num[MAXN],father[MAXN],siz[MAXN],cnt=0;struct Node1{    int next,to;}Edges[MAXN*2];void addedge(int u,int v){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;}int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}void dfs1(int u){    siz[u]=1;    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==father[u])continue;        father[v]=u,dep[v]=dep[u]+1;        dfs1(v);        siz[u]+=siz[v];    }}void dfs2(int u,int t){    sz++,pos[u]=sz,num[sz]=u;    int maxv=0,k=0;    top[u]=t;    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==father[u])continue;        if(siz[v]>maxv)maxv=siz[v],k=v;    }    if(k)dfs2(k,t);    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==father[u]||v==k)continue;        dfs2(v,v);    }}struct Node2{    int l,r,sum,maxn;}t[MAXN*4];void build(int idx,int l,int r){    t[idx].l=l,t[idx].r=r;    if(l==r)    {        t[idx].sum=t[idx].maxn=w[num[l]];        return;    }    int mid=(l+r)>>1;    build(idx<<1,l,mid);    build(idx<<1|1,mid+1,r);    t[idx].maxn=max(t[idx<<1].maxn,t[idx<<1|1].maxn);    t[idx].sum=t[idx<<1].sum+t[idx<<1|1].sum;}int query1(int idx,int a,int b){    if(a<=t[idx].l&&b>=t[idx].r)    return t[idx].maxn;    int mid=(t[idx].l+t[idx].r)>>1;    if(b<=mid)return query1(idx<<1,a,b);    if(a>mid)return query1(idx<<1|1,a,b);    return max(query1(idx<<1,a,b),query1(idx<<1|1,a,b));}int query2(int idx,int a,int b){    if(a<=t[idx].l&&b>=t[idx].r)    return t[idx].sum;    int mid=(t[idx].l+t[idx].r)>>1;    if(b<=mid)return query2(idx<<1,a,b);    if(a>mid)return query2(idx<<1|1,a,b);    return query2(idx<<1,a,b)+query2(idx<<1|1,a,b);}void change(int idx,int a,int b){    if(t[idx].l==t[idx].r){t[idx].maxn=t[idx].sum=b;return;}    int mid=(t[idx].l+t[idx].r)>>1;    if(a<=mid)change(idx<<1,a,b);    else change(idx<<1|1,a,b);    t[idx].maxn=max(t[idx<<1].maxn,t[idx<<1|1].maxn);    t[idx].sum=t[idx<<1].sum+t[idx<<1|1].sum;}void QMAX(int a,int b){    ans=-INF;    while(top[a]!=top[b])    {        if(dep[top[a]]
          
           pos[b])swap(a,b);    ans=max(ans,query1(1,pos[a],pos[b]));    printf("%d\n",ans);}void QSUM(int a,int b){    ans=0;    while(top[a]!=top[b])    {        if(dep[top[a]]
           
            pos[b])swap(a,b); ans+=query2(1,pos[a],pos[b]); printf("%d\n",ans);} int main(){ memset(head,-1,sizeof(head)); n=read(); for(int i=1;i

View Code

2.0 Tarjan离线LCA

2.1 倍增LCA

3.0 点分治（BZOJ2152 聪聪可可）

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 20005#define INF 0x3f3f3f3fusing namespace std;int n,head[MAXN],siz[MAXN],maxv[MAXN],root=0,tot=0,num=0,cnt=0,t[3],p,q;bool vis[MAXN];int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct Node{    int next,to,w;}Edges[MAXN*2];int gcd(int a,int b){
    return b?gcd(b,a%b):a;}void addedge(int u,int v,int w){    Edges[cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;    Edges[cnt++].w=w;}void getroot(int u,int f){    siz[u]=1,maxv[u]=0;    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==f||vis[v])continue;        getroot(v,u);        siz[u]+=siz[v],maxv[u]=max(maxv[u],siz[v]);    }    maxv[u]=max(maxv[u],tot-siz[u]);    if(maxv[u]

View Code

数据结构

1.0 splay（BZOJ3223 Tyvj 1729 文艺平衡树）

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m,a[100005],root,siz=0;struct Node{    int ch[2],father,val,rev,siz;}t[100005];inline int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}void Update(int x){    t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;}void Pushdown(int x){    if(t[x].rev)    {        t[x].rev=0;        if(t[x].ch[0])t[t[x].ch[0]].rev^=1;        if(t[x].ch[1])t[t[x].ch[1]].rev^=1;        swap(t[x].ch[0],t[x].ch[1]);    }}void Rotate(int x,int &k){    Pushdown(x);    int y=t[x].father,z=t[y].father;    int p=(t[y].ch[0]==x)?0:1;    if(y!=k)    {        if(t[z].ch[0]==y)t[z].ch[0]=x;        else t[z].ch[1]=x;    }    else k=x;    t[x].father=z;    t[y].ch[p]=t[x].ch[p^1];    t[t[x].ch[p^1]].father=y;    t[x].ch[p^1]=y;    t[y].father=x;    Update(y),Update(x);}void Splay(int x,int &k){    while(x!=k)    {        int y=t[x].father,z=t[y].father;        if(y!=k)        {            if((t[y].ch[0]==x)^(t[z].ch[0]==y))            Rotate(x,k);            else Rotate(y,k);        }        Rotate(x,k);    }}int Build(int l,int r,int f){    if(l>r)return 0;    int mid=(l+r)>>1,now=++siz;    t[now].father=f;    t[now].rev=0;    t[now].val=mid;    t[now].ch[0]=Build(l,mid-1,now);    t[now].ch[1]=Build(mid+1,r,now);    Update(now);    return now;}int Find(int x,int k){    if(!k)return 0;    Pushdown(x);    if(t[t[x].ch[0]].siz>=k)return Find(t[x].ch[0],k);    else if(t[t[x].ch[0]].siz+1

View Code

1.1 treap（BZOJ3224 TYVJ 1728 普通平衡树）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,siz=0,root=0,ans;struct Node{    int lch,rch,val,siz,w,rank;}t[100005];inline int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();     }    return x*f;}void update(int k){    t[k].siz=t[t[k].lch].siz+t[t[k].rch].siz+t[k].w;}void leftRotate(int &k){    int p=t[k].rch;    t[k].rch=t[p].lch;    t[p].lch=k;    t[p].siz=t[k].siz;    update(k);k=p;}void rightRotate(int &k){    int p=t[k].lch;    t[k].lch=t[p].rch;    t[p].rch=k;    t[p].siz=t[k].siz;    update(k);k=p;}void Insert(int &k,int x){    if(!k){        siz++;k=siz;        t[k].siz=t[k].w=1;        t[k].val=x;        t[k].rank=rand();        return;    }    t[k].siz++;    if(t[k].val==x)    {t[k].w++;return;}    if(x
           
            1) {t[k].siz--;t[k].w--;return;} if(!t[k].lch||!t[k].rch) {k=t[k].lch+t[k].rch;return;} if(t[t[k].lch].rank>t[t[k].rch].rank){ leftRotate(k);Delete(k,x); return; } else{ rightRotate(k);Delete(k,x); return; } } t[k].siz--; if(x
            
             t[t[k].lch].siz+t[k].w)return queryNum(t[k].rch,x-t[t[k].lch].siz-t[k].w); else return t[k].val;}void queryPre(int k,int x){ if(!k)return; if(x<=t[k].val)queryPre(t[k].lch,x); else {ans=t[k].val,queryPre(t[k].rch,x);}}void querySuc(int k,int x){ if(!k)return; if(x>=t[k].val)querySuc(t[k].rch,x); else {ans=t[k].val,querySuc(t[k].lch,x);}}int main(){ srand(time(0)); n=read(); for(int i=1;i<=n;i++) { int opt,x; opt=read(),x=read(); switch(opt) { case 1:Insert(root,x);break; case 2:Delete(root,x);break; case 3:printf("%d\n",queryRank(root,x));break; case 4:printf("%d\n",queryNum(root,x));break; case 5:ans=0;queryPre(root,x);printf("%d\n",ans);break; case 6:ans=0;querySuc(root,x);printf("%d\n",ans);break; } } return 0;}

View Code

图论

1.0 强连通分量

void tarjan(int u){    dfn[u]=low[u]=++dfn_clock;    vis[u]=ins[u]=1;s.push(u);    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(!vis[v])        {            tarjan(v);            low[u]=min(low[u],low[v]);        }        else if(ins[v])        {low[u]=min(low[u],dfn[v]);}    }    if(dfn[u]==low[u])    {        tot++;int t=-1;        while(t!=u)        {            t=s.top();            sccno[t]=tot;            ins[t]=0;            s.pop();        }    }}

View Code

1.1 割点

1.2 割边

2.0 Dinic （草地排水）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define INF 0x3f3f3f3f#define MAXN 250using namespace std;int m,n,s,t,level[MAXN],head[MAXN],cnt=0;struct Node{    int next,to,cap;}Edges[MAXN*2];void addedge(int u,int v,int c){    Edges[cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;    Edges[cnt++].cap=c;}void insert(int u,int v,int c){    addedge(u,v,c);    addedge(v,u,0);}bool bfs(){    memset(level,-1,sizeof(level));    level[s]=0;    queue
           
            q; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==-1&&Edges[i].cap) level[v]=level[u]+1,q.push(v); } } if(level[t]==-1)return false; return true;}int dfs(int u,int flow){ int f=0,d=0; if(u==t)return flow; for(int i=head[u];~i&&flow>f;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==level[u]+1&&Edges[i].cap) { d=dfs(v,min(flow-f,Edges[i].cap)); f+=d; Edges[i].cap-=d; Edges[i^1].cap+=d; } } if(!f)level[u]=-1; return f;}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d",&m,&n); s=1,t=n; for(int i=1;i<=m;i++) { int u,v,c; scanf("%d%d%d",&u,&v,&c); insert(u,v,c); } int ans=0,d; while(bfs()) { while(d=dfs(s,INF)) ans+=d; } printf("%d",ans); return 0;}

View Code

2.1 费用流

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define INF 0x3f3f3f3fusing namespace std;int m,n,s,t,a[450],pre[450],dis[450],head[450],cnt=0,MF,MC;bool inq[450];struct Node{    int next,from,to,cap,w;}Edges[30005];void addedge(int u,int v,int c,int w){    Edges[cnt].next=head[u];    head[u]=cnt;    Edges[cnt].from=u;    Edges[cnt].to=v;    Edges[cnt].cap=c;    Edges[cnt++].w=w;}void insert(int u,int v,int c,int w){    addedge(u,v,c,w);    addedge(v,u,0,-w);}void MCMF(){    MF,MC=0;    while(1)    {        memset(dis,0x3f,sizeof(dis));        memset(a,0,sizeof(a));        int f=0;        queue
           
            q; q.push(s); inq[s]=1,a[s]=INF,dis[s]=0; while(!q.empty()) { int u=q.front();q.pop();inq[u]=0; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(dis[u]+Edges[i].w
            
             0) { dis[v]=dis[u]+Edges[i].w; a[v]=min(a[u],Edges[i].cap); pre[v]=i; if(!inq[v]){q.push(v);inq[v]=1;} } } } if(a[t]==0)break; int p=t; MC+=a[t]*dis[t]; while(p!=s){ Edges[pre[p]].cap-=a[t]; Edges[pre[p]^1].cap+=a[t]; p=Edges[pre[p]].from; } MF+=a[t]; }}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); s=1,t=n; for(int i=1;i<=m;i++) { int u,v,c,w; scanf("%d%d%d%d",&u,&v,&c,&w); insert(u,v,c,w); } MCMF(); printf("%d %d\n",MF,MC); return 0;}

View Code

3.0 匈牙利算法（UOJ#78. 二分图最大匹配）

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n1,n2,m,head[505],cnt=0,ans=0,link[505];bool vis[505];struct Node{    int next,to;}Edges[250005];void addedge(int u,int v){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;}int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}bool dfs(int u){    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(!vis[v])        {            vis[v]=1;            if(!link[v]||dfs(link[v]))            {link[v]=u;return true;}        }    }    return false;}int main(){    memset(head,-1,sizeof(head));    n1=read(),n2=read(),m=read();    for(int i=1;i<=m;i++)    {        int v=read(),u=read();        addedge(u,v);    }    for(int i=1;i<=n2;i++)    {        memset(vis,0,sizeof(vis));        if(dfs(i))ans++;    }    printf("%d\n",ans);    for(int i=1;i<=n1;i++)    printf("%d ",link[i]);    return 0;}

View Code

字符串

1.0 KMP

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 1000005using namespace std;int n,m,next[MAXN],cnt=0;char a[MAXN],b[MAXN];int main(){    scanf("%s%s",a+1,b+1);    n=strlen(a+1),m=strlen(b+1);    int j=0;next[1]=0;    for(int i=2;i<=m;i++)    {        while(j!=0&&b[i]!=b[j+1])j=next[j];        if(b[i]==b[j+1])j++;        next[i]=j;    }    j=0;    for(int i=1;i<=n;i++)    {        while(j!=0&&a[i]!=b[j+1])j=next[j];        if(a[i]==b[j+1])j++;        if(j==m){j=next[j],++cnt;}    }    printf("%d\n",cnt);    return 0;}

View Code

2.0 AC自动机（BZOJ3172 TJOI2013 单词）

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,siz,root,q[1000010],head,tail,pos[202];char word[1000010];struct Node{    int next[26],cnt,fail;    bool vis;}trie[1000010];int newnode(){    siz++;    trie[siz].cnt=trie[siz].fail=trie[siz].vis=0;    memset(trie[siz].next,0,sizeof(trie[siz].next));    return siz;}void insert(int x,char* word){    int i=0,p=root;    while(word[i])    {        int idx=word[i]-'a';        if(!trie[p].next[idx])trie[p].next[idx]=newnode();        p=trie[p].next[idx];        trie[p].cnt++;        i++;    }    pos[x]=p;}void build(){    head=0,tail=0;    q[++tail]=root;    while(head
          
           0;p--)    {        int t=trie[q[p]].fail;        trie[t].cnt+=trie[q[p]].cnt;    }    for(int i=1;i<=n;i++)    printf("%d\n",trie[pos[i]].cnt);}int main(){    scanf("%d",&n);    siz=0,root=newnode();    for(int i=1;i<=n;i++)    {        scanf("%s",word);        insert(i,word);    }    build();work();    return 0;}

View Code

3.0 Manachar

4.0 SAM

5.0 SA

计算几何

1.0 点和直线

int dcmp(double x){        //实数比较     if(fabs(x)
      
       0?1:-1;}struct Point{        //点\向量的定义     double x,y;    Point(double x=0,double y=0):x(x),y(y){}    Point operator + (Point A){
    return Point(x+A.x,y+A.y);}    Point operator - (Point A){
    return Point(x-A.x,y-A.y);}    Point operator * (double p){
    return Point(x*p,y*p);}    Point operator / (double p){
    return Point(x/p,x/p);}        bool operator == (Point A){
    return dcmp(x-A.x)==0&&dcmp(y-A.y)==0;}};typedef Point Vector;double dot(Vector A,Vector B){        //点积     return A.x*B.x+A.y*B.y;}double cross(Vector A,Vector B){    //叉积     return A.x*B.y-B.x*A.y;}double length(Vector A){        //向量的长度     return sqrt(dot(A,A));}double angle(Vector A,Vector B){        //两向量的转角     return acos(dot(A,B)/length(A)/length(B));}Vector rotate(Vector A,double rad){        //向量的旋转     return Vector(cos(rad)*A.x-sin(rad)*A.y,sin(rad)*A.x+cos(rad)*A.y);}Vector normal(Vector A){        //法向量     double l=length(A);    return Vector(-A.y/l,A.x/l);}struct Line{        //线     Point p;Vector v;    Line(Point p=Point(0,0),Vector v=Vector(0,0)):p(p),v(v){}};Point get_intersection(Line A,Line B){        //两直线求交     Point u=A.p-B.p;    double t=cross(B.v,u)/cross(A.v,B.v);    return A.p+A.v*t;}double dis_line(Point P,Point A,Point B){        //点到直线的距离     Vector v1=B-A,v2=P-A;    return fabs(cross(v1,v2)/length(v1));}double dis_segment(Point P,Point A,Point B){        //点到线段的距离     Vector v1=B-A,v2=P-A,v3=P-B;    if(dcmp(dot(v1,v2)<0))return length(v2);    if(dcmp(dot(v1,v3)>0))return length(v3);     return fabs(cross(v1,v2)/length(v1));}Point get_projection(Point P,Point A,Point B){        //点在直线上的投影     Vector v=B-A;     return A+v*(dot(P-A,v)/dot(v,v)); } bool segment_properintersection(Point a1,Point a2,Point b1,Point b2)    //线段相交判定 {    double c1=cross(b2-b1,a1-b1),c2=cross(b2-b1,a2-b1),    c3=cross(a2-a1,b1-a1),c4=cross(a2-a1,b2-a1);    return dcmp(c1)*dcmp(c2)<=0&&dcmp(c3)*dcmp(c4)<=0;}

View Code

2.0 圆

struct Circle{    Point c;double r;    Point getpoint(double ang){        //获取圆上弧度角为ang的点         return Point(c.x+r*cos(ang),c.y+r*sin(ang));    }};int getLineCircle_intersection(Line L,Circle C,double& t1,double& t2,vector
      
       & sol){    double a=L.v.x,b=L.p.x-C.c.x,c=L.v.y,d=L.p.y-C.c.y;        //直线与圆的交点     double e=a*a+c*c,f=2*a*b+2*c*d,g=b*b+d*d-C.r*C.r;    double delta=(f*f)-4*e*g;    if(dcmp(delta)<0)return 0;    if(!dcmp(delta)){        t1=-f/(2*e);sol.push_back(L.p+L.v*t1);        return 1;    }    t1=-f+sqrt(delta)/(2*e);t2=-f-sqrt(delta)/(2*e);    sol.push_back(L.p+L.v*t1);sol.push_back(L.p+L.v*t2);    return 2;}double angle(Vector A){        //极角     return atan2(A.y,A.x);}int getCircleCircle_intersection(Circle C1,Circle C2,vector
       
        & sol){            double d=length(C1.c-C2.c);        //两圆交点     if(dcmp(C1.r+C2.r-d)<0)return 0;    if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;    double a=angle(C2.c-C1.c);    double da=acos((d*d+C1.r*C1.r-C2.r*C2.r)/(2*d*C1.r));    Point p1=C1.getpoint(a+da),p2=C1.getpoint(a-da);    if(p1==p2){        sol.push_back(p1);return 1;    };    sol.push_back(p1),sol.push_back(p2);    return 2;}int get_tangents(Point p,Circle C,vector
        
         & sol){    Vector u=C.c-p;        //切线     double dis=length(u);    if(dcmp(dis-C.r)<0)return 0;    if(!dcmp(dis-C.r)){        sol.push_back(rotate(u,pi/2));return 1;    }    double ang=asin(C.r/dis);    sol.push_back(rotate(u,ang));sol.push_back(rotate(u,-ang));    return 2;}

View Code

3.0 凸包

4.0 半平面交

5.0 自适应Simpson积分

double simpson(double a,double b){    double c=a+(b-a)/2;    return (F(a)+4*F(c)+F(b))*(b-a)/6.0;}double asr(double a,double b,double eps,double A){    double c=a+(b-a)/2;    double L=simpson(a,c),R=simpson(c,b);    if(fabs(L+R-A)

View Code

6.0 旋转卡壳

数学

1.0 欧几里得算法

LL gcd(LL a,LL b){    return (b==0)?a:gcd(b,a%b);}

View Code

1.1 扩展欧几里得算法

void exgcd(LL a,LL b,LL& d,LL& x,LL& y){    if(!b){d=a,x=1,y=0;}    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}}

View Code

2.0 乘法逆元

LL inv(LL a,LL p){    LL d,x,y;    exgcd(a,p,d,x,y);    return (d==1)?(x+p)%p:-1;}

View Code

3.0 FFT（UOJ#34. 多项式乘法）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 400005#define pi acos(-1)using namespace std;int n,m;struct cp{    double r,i;    cp(double r=0,double i=0):r(r),i(i){}    cp operator + (const cp& A)    {
     return cp(r+A.r,i+A.i);}    cp operator - (const cp& A)    {
     return cp(r-A.r,i-A.i);}    cp operator * (const cp& A)    {
     return cp(r*A.r-i*A.i,r*A.i+i*A.r);}}a[MAXN],b[MAXN];void brc(cp* x,int l){    int k=l/2;    for(int i=1;i
           
            >=1; } if(k

View Code

4.0 NTT

5.0 欧拉函数

void phi_table(){    phi[1]=1;    for(int i=1;i<=n;i++)    {        if(!phi[i])        for(int j=i;j<=n;j+=i)        {            if(!phi[j])phi[j]=j;            phi[j]=phi[j]*(i-1)/i;        }    }}

View Code

6.0 中国剩余定理（CodeVS 3990 中国余数定理 2）

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;LL n,a,b,c[15],m[15],M=1,res=0;LL read(){    LL x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
     if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}void exgcd(LL a,LL b,LL &x,LL &y){    if(!b)x=1,y=0;    else exgcd(b,a%b,y,x),y-=x*(a/b);}int main(){    n=read(),a=read(),b=read();    for(int i=1;i<=n;i++)    m[i]=read(),c[i]=read(),M*=m[i];    for(int i=1;i<=n;i++)    {        LL t=M/m[i],x,y;        exgcd(t,m[i],x,y);        x=(x+m[i])%m[i];        res=(res+((x*t)%M*c[i])%M)%M;    }    if(a>res)    {        if((a-res)%M==0)res+=(a-res)/M*M;        else res+=((a-res)/M+1)*M;    }    if(res>b||res

View Code

6.1 扩展中国剩余定理（POJ 2891 Strange Way to Express Integers）

#include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 50005using namespace std;typedef long long LL;LL k,c[MAXN],m[MAXN];LL read(){    LL x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
     if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}LL gcd(LL a,LL b){
      return b?gcd(b,a%b):a;}void exgcd(LL a,LL b,LL &d,LL &x,LL& y){    if(!b)d=a,x=1,y=0;    else exgcd(b,a%b,d,y,x),y-=x*(a/b);}LL inv(LL a,LL p){    LL d,x,y;exgcd(a,p,d,x,y);    return (x+p)%p==0?p:(x+p)%p;}int main(){    LL m1,m2,c1,c2;    while(~scanf("%lld",&k))    {        for(int i=1;i<=k;i++)            m[i]=read(),c[i]=read();        for(int i=2;i<=k;i++)        {            m1=m[i-1],m2=m[i],c1=c[i-1],c2=c[i];            LL t=gcd(m1,m2);            if((c2-c1)%t!=0){c[k]=-1;break;}            m[i]=m1*m2/t;            c[i]=inv(m1/t,m2/t)*((c2-c1)/t)%(m2/t)*m1+c1;            c[i]=(c[i]%m[i]+m[i])%m[i];        }        printf("%lld\n",c[k]);    }    return 0;}