SDOI前的小计划

upd：19.4.5 放出来了。如果明天考了我没复习到的认了。考到了复习了的还没拿到理想分的就回来谢罪（bushi

www

SDOI一轮倒计时4天啦w

所以得有个小计划吧QwQ

4.2

目标：BZOJ5407

模板：

✔最小树形图

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define M 10010

#define N 110

#define totsize sizeof(int)*(n+1)

using namespace std;

struct edge{int u,v,w;}e[M];

int id[N],mn[N],pre[N],vis[N];

int n,m;

int zlal(int rt)

{

    int res=;

    while()

    {

        for(int i=;i<=n;i++)    mn[i]=inf;

        for(int i=;i<=m;i++)

            if(e[i].u!=e[i].v && e[i].w<mn[e[i].v])

                mn[e[i].v]=e[i].w,pre[e[i].v]=e[i].u;

        for(int i=;i<=n;i++)    if(i!=rt)

            if(mn[i]==inf)    return -;

        int tn=,u,v;

        memset(id,,totsize); memset(vis,,totsize);

        mn[rt]=;

        for(int i=;i<=n;i++)

        {

            res+=mn[i]; v=i;

            while(v!=rt&&!id[v]&&vis[v]!=i)

                vis[v]=i,v=pre[v];

            if(v!=rt&&!id[v])

            {

                ++tn;

                for(u=pre[v];u!=v;u=pre[u])

                    id[u]=tn;

                id[v]=tn;

            }

        }

        if(!tn)    return res;

        for(int i=;i<=n;i++)    if(!id[i])

            id[i]=++tn;

        for(int i=;i<=m;i++)

        {

            int v=e[i].v;

            e[i].u=id[e[i].u];

            e[i].v=id[e[i].v];

            if(e[i].u!=e[i].v)

                e[i].w-=mn[v];

        }

        n=tn; rt=id[rt];

    }

}

int main()

{

    int r; scanf("%d%d%d",&n,&m,&r);

    for(int i=;i<=m;i++)    scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    printf("%d\n",zlal(r));

    return ;

}

✔主席树

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define N 200010

using namespace std;

int read()

{

    int s=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')    f=-; ch=getchar();}

    while(ch>=''&&ch<='')    s=s*+ch-'',ch=getchar();

    return s;

}

struct node{int ls,rs,s;};

struct SGT

{

    node t[N*]; int poi;

    void pushup(int x){t[x].s=t[t[x].ls].s+t[t[x].rs].s;}

    void build(int &x,int l,int r)

    {

        x=++poi; if(l==r)    return; int mid=l+r>>;

        build(t[x].ls,l,mid); build(t[x].rs,mid+,r);

    }

    void modify(int &x,int l,int r,int lt,int d)

    {

        x=++poi; t[x]=t[lt]; t[x].s++;

        if(l==r)    return; int mid=l+r>>;

        if(d<=mid)    modify(t[x].ls,l,mid,t[lt].ls,d);

        else    modify(t[x].rs,mid+,r,t[lt].rs,d);

    }

    int query(int x,int y,int l,int r,int d)

    {

        if(l==r)    return l;

        int s=t[t[y].ls].s-t[t[x].ls].s,mid=l+r>>;

        if(s>=d)    return query(t[x].ls,t[y].ls,l,mid,d);

        else    return query(t[x].rs,t[y].rs,mid+,r,d-s);

    }

}sgt;

int a[N],rt[N],n,m,h[N];

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++)    a[i]=read(),h[i]=a[i];

    sort(h+,h+n+); int nn=unique(h+,h+n+)-h-; sgt.build(rt[],,nn);

    for(int i=;i<=n;i++)    a[i]=lower_bound(h+,h+nn+,a[i])-h,sgt.modify(rt[i],,nn,rt[i-],a[i]);

    for(int i=;i<=m;i++)

    {

        int l,r,k; l=read(); r=read(); k=read();

        printf("%d\n",h[sgt.query(rt[l-],rt[r],,nn,k)]);

    }

    return ;

}

（菜死了 11min才写完还手贱wa了一发QAQ）

✔Tarjan 割点/缩点

✔FFT（快读神tm加速1/4）

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define db double

#define N 4000100

using namespace std;

const db pi=acos(-1.0);

int read()

{

    char ch=getchar(); int s=;

    while(ch>''||ch<'')    ch=getchar();

    while(ch>=''&&ch<='')    s=s*+ch-'',ch=getchar();

    return s;

}

struct cpx

{

    db x,y;

    cpx(){}

    cpx(db xx,db yy){x=xx,y=yy;}

};

cpx operator+(cpx a,cpx b){return cpx(a.x+b.x,a.y+b.y);}

cpx operator-(cpx a,cpx b){return cpx(a.x-b.x,a.y-b.y);}

cpx operator*(cpx a,cpx b){return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

int rev[N];

int pre(int n)

{

    int lim=,l=;

    while(lim<n)    lim<<=,l++;

    for(int i=;i<lim;i++)

        rev[i]=(rev[i>>]>>)|((i&)<<(l-));

    return lim;

}

void fft(cpx *a,int lim,bool f)

{

    for(int i=;i<lim;i++)    if(rev[i]>i)

        swap(a[i],a[rev[i]]);

    for(int k=,mid=;k<=lim;mid<<=,k<<=)

    {

        cpx Wn=cpx(cos(pi/mid),sin(pi/mid));

        if(f)    Wn.y=-Wn.y;

        for(int i=;i<lim;i+=k)

        {

            cpx w=cpx(1.0,0.0);

            for(int j=;j<mid;j++,w=w*Wn)

            {

                cpx x=a[i+j],y=w*a[i+j+mid];

                a[i+j]=x+y,a[i+j+mid]=x-y;

            }

        }

    }

}

cpx f[N],g[N];

int main()

{

    int n,m; n=read(); m=read(); n++;m++;

    for(int i=;i<n;i++)    f[i].x=read();

    for(int i=;i<m;i++)    g[i].x=read();

    int lim=pre(n+m); fft(f,lim,); fft(g,lim,);

    for(int i=;i<lim;i++)    f[i]=f[i]*g[i];

    fft(f,lim,);

    for(int i=;i<n+m-;i++)    printf("%d ",(int)(f[i].x/lim+0.5));

    return ;

}

✔NTT

✔多项式求逆

✔多项式ln

✔多项式exp

✔多项式除法　　

✔多项式开根

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define N 400100

#define mdn 998244353

#define G 3

using namespace std;

int read()

{

    char ch=getchar(); int s=;

    while(ch>''||ch<'')    ch=getchar();

    while(ch<=''&&ch>='')    s=s*+ch-'',ch=getchar();

    return s;

}

int rev[N];

int f[N];

int ksm(int bs,int mi)

{

    int ans=;

    while(mi)

    {

        if(mi&)    ans=(ll)ans*bs%mdn;

        bs=(ll)bs*bs%mdn; mi>>=;

    }

    return ans;

}

int inv;

int pre(int n)

{

    int lim=,l=;

    while(lim<n)    lim<<=,l++;

    for(int i=;i<lim;i++)

        rev[i]=(rev[i>>]>>)|((i&)<<(l-));

    inv=ksm(lim,mdn-);

    return lim;

}

void NTT(int *a,int lim,int f)

{

    for(int i=;i<lim;i++)    if(rev[i]<i)

        swap(a[rev[i]],a[i]);

    for(int k=,mid=;k<=lim;mid<<=,k<<=)

    {

        int Wn=ksm(G,(mdn-)/k); if(f)    Wn=ksm(Wn,mdn-);

        for(int i=,w=;i<lim;i+=k,w=)

            for(int j=;j<mid;j++,w=(ll)w*Wn%mdn)

            {

                int x=a[i+j],y=(ll)w*a[i+j+mid]%mdn;

                a[i+j]=x+y>=mdn?x+y-mdn:x+y;

                a[i+j+mid]=x-y<?x-y+mdn:x-y;

            }

    }

    if(f)    for(int i=;i<lim;i++)    a[i]=(ll)a[i]*inv%mdn;

}

/**

poly_inv

求 f*g=1(% x^n)

因此 g=1(% x^[n/2])

已知 f*h=1(% x^[n/2])

可得 g-h=0(% x^[n/2])

平方 g^2+h^2-2g*h=0(% x^n)

左乘f得到 g=2fh-fh^2(% x^n)

递归求解

*/

struct poly_inv

{

    int g[N],h[N];

    void inv(int *a,int n)

    {

        if(n==){g[]=ksm(a[],mdn-);return;}

        int mid=(n+)>>; inv(a,mid); int lim=pre(n<<);

        for(int i=;i<n;i++)    h[i]=a[i];

        for(int i=n;i<lim;i++)    h[i]=;

        NTT(h,lim,); NTT(g,lim,);

        for(int i=;i<lim;i++)

            g[i]=(2ll-(ll)g[i]*h[i]%mdn+mdn)%mdn*g[i]%mdn;

        NTT(g,lim,);

        for(int i=n;i<lim;i++)    g[i]=;

    }

    void print(int n)

    {

        for(int i=;i<n;i++)    printf("%d ",g[i]);

    }

}INV;

/**

poly_ln

求g=ln(f)

对复合函数g(f)求导

(ln(f))'=ln'(f)f'=(1/f)*f'

即 g'=1/f*f'

积分回去就行了

*/

struct poly_ln

{

    int g[N],h[N];

    void ln(int *a,int n)

    {

        INV.inv(a,n);

        for(int i=;i<n;i++)    g[i]=INV.g[i];

        for(int i=;i<n;i++)    h[i-]=(ll)f[i]*i%mdn;

        int lim=pre(n<<); NTT(g,lim,); NTT(h,lim,);

        for(int i=;i<lim;i++)    h[i]=(ll)g[i]*h[i]%mdn;

        NTT(h,lim,);

        for(int i=;i<n;i++)    g[i+]=(ll)h[i]*ksm(i+,mdn-)%mdn;

        g[]=;

    }

    void print(int n)

    {

        for(int i=;i<n;i++)    printf("%d ",g[i]);

    }

}LN;

/**

poly_exp

求 g=e^f

根据牛顿迭代+泰勒展开

可以得到

h(f)=0(% x^n)

展开一次【开方 h(f0)=0(% x^n/2)

h(f0)+h'(f0)(f-f0)=0(% x^n)

移项 f=f0-h(f0)/h'(f0)

由于我们求的g=e^f 取h为lng-f=0(% x^n)

所以带进去就是 g=g0-(lng0-f)/lng0=g0*(1-lng0+f)

*/

struct poly_exp

{

    int s[N],g[N],tmp[N];

    void exp(int *a,int n)

    {

        if(n==){s[]=;return;}

        int mid=n+>>; exp(a,mid);

        for(int i=;i<(n<<);i++)    g[i]=;

        LN.ln(g,n);

        for(int i=;i<n;i++)    g[i]=LN.g[i],tmp[i]=a[i];

        int lim=pre(n<<);

        NTT(g,lim,);NTT(tmp,lim,);NTT(s,lim,);

        for(int i=;i<lim;i++)

            s[i]=((ll)tmp[i]-g[i]++mdn)%mdn*s[i]%mdn;

        NTT(s,lim,);

        for(int i=n;i<lim;i++)    g[i]=tmp[i]=;

    }

    void print(int n)

    {

        for(int i=;i<n;i++)    printf("%d ",s[i]);

    }

}EXP;

/**

poly_div

通过系数翻转

f n次 g m次

f=g*h+r

fR=x^nf(1/x)

所以全部翻转再左乘x^n

可以得到

x^nfR=x^mgR*x^(n-m)hR+x^(n-m+1)*x^(m-1)rR

其实就是

fR=gR*hR+x^(n-m+1)rR

于是我们可以在%x^(n-m+1)意义下先求逆得到hR

然后翻回去求r

*/

int main()

{

    int n; n=read();

    for(int i=;i<n;i++)    f[i]=read();

    EXP.exp(f,n); EXP.print(n);

    return ;

}

（写了前三个 exp懒得调了发现还要清前面的ln啥的就扔在那看看吧QAQ）（多项式除法没写QAQ）

✔左偏树

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define N 100010

using namespace std;

int read()

{

    int f=,s=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')    f=-;ch=getchar();}

    while(ch>=''&&ch<='')    s=s*+ch-'',ch=getchar();

    return f*s;

}

struct node{int val,fa,son[],dis; bool tag;}t[N];

int find(int x){return t[x].fa^x?t[x].fa=find(t[x].fa):x;}

int merge(int x,int y)

{

    if(!x||!y)    return x|y;

    if(t[y].val<t[x].val||(t[y].val==t[x].val&&y<x)) swap(x,y);

    t[x].son[]=merge(t[x].son[],y);

    t[t[x].son[]].fa=t[t[x].son[]].fa=x; t[x].fa=x;

    if(t[t[x].son[]].dis>t[t[x].son[]].dis)    swap(t[x].son[],t[x].son[]);

    t[x].dis=t[t[x].son[]].dis+;

    return x;

}

void pop(int x)

{

    t[x].tag=; printf("%d\n",t[x].val);

    t[t[x].son[]].fa=t[x].son[]; t[t[x].son[]].fa=t[x].son[];

    t[x].fa=merge(t[x].son[],t[x].son[]);

}

int n,m;

int main()

{

    n=read(); m=read(); int opt,x,y;

    for(int i=;i<=n;i++)    t[i].val=read(),t[i].fa=i;

    for(int i=;i<=m;i++)

    {

        opt=read(); x=read();

        if(opt==)

        {

            y=read(); if(t[x].tag||t[y].tag)    continue;

            x=find(x); y=find(y); if(x==y)    continue;

            merge(x,y);

        }

        else

        {

            if(t[x].tag){printf("-1\n"); continue;}

            x=find(x); pop(x);

        }

    }

    return ;

}

✔KD树

✔圆方树

✔FWT

/**

OR

FWT(A)=(FWT(A0),FWT(A0+A1))

IFWT(A)=(IFWT(A0),IFWT(A1-A0))

*/

/**

AND

FWT(A)=(FWT(A0+A1),FWT(A1))

IFWT(A)=(IFWT(A0-A1),IFWT(A1))

*/

/**

XOR

FWT(A)=(FWT(A0+A1),FWT(A0-A1))

IFWT(A)=(IFWT(A0+A1)/2,IFWT(A0-A1)/2)

*/

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define N 2000100

#define mdn 998244353

using namespace std;

int read()

{

    int s=,f=; char ch=getchar();

    while(ch>''||ch<''){if(ch=='-') f=-;ch=getchar();}

    while(ch<=''&&ch>='')    s=s*+ch-'',ch=getchar();

    return (s*f%mdn+mdn)%mdn;

}

int a[N],b[N],c[N]; int inv=;

void fwt(int *a,int top,int type)

{

    for(int k=,mid=;k<=top;k<<=,mid<<=)

        for(int i=;i<top;i+=k)    for(int j=;j<mid;j++)

        {

            int x=a[i+j],y=a[i+j+mid];

            if(type==) a[i+j]=x,a[i+j+mid]=(x+y)%mdn;

            else if(type==) a[i+j]=(x+y)%mdn,a[i+j+mid]=y;

            else if(type==) a[i+j]=(x+y)%mdn,a[i+j+mid]=(x-y+mdn)%mdn;

            else if(type==-) a[i+j]=x,a[i+j+mid]=(y-x+mdn)%mdn;

            else if(type==-) a[i+j]=(x-y+mdn)%mdn,a[i+j+mid]=y;

            else if(type==-) a[i+j]=(ll)(x+y)%mdn*inv%mdn,a[i+mid+j]=((ll)(x-y)%mdn*inv%mdn+mdn)%mdn;

        }

}

int top;

void query(int type)

{

    fwt(a,top,type); fwt(b,top,type);

    for(int i=;i<top;i++)    c[i]=(ll)a[i]*b[i]%mdn;

    fwt(c,top,-type); fwt(a,top,-type); fwt(b,top,-type);

    for(int i=;i<top;i++)    printf("%d ",c[i]);

    printf("\n");

}

int main()

{

    int n;

    scanf("%d",&n); top=<<n;

    for(int i=;i<top;i++)    scanf("%d",&a[i]);

    for(int i=;i<top;i++)    scanf("%d",&b[i]);

    query(); query(); query();

    return ;

}

✔0/1分数规划

✔后缀自动机

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define N 1000100

using namespace std;

struct node{int ch[],fa,len,sz;}t[N*];

struct edge{int to,lt;}e[N*];

char ch[N]; int in[N*],cnt,lt,rt,poi,ans,n;

void add(int x,int y){e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;}

int id(char c){return c-'a';}

void insert(int c)

{

    int p=lt,np=lt=++poi; t[np].len=t[p].len+; t[np].sz=;

    for(;p&&!t[p].ch[c];p=t[p].fa)    t[p].ch[c]=np;

    if(!p){t[np].fa=rt; return;}

    int q=t[p].ch[c];

    if(t[q].len==t[p].len+){t[np].fa=q; return;}

    int nq=++poi; t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq;

    memcpy(t[nq].ch,t[q].ch,sizeof(t[nq].ch)); t[nq].len=t[p].len+;

    for(;p&&t[p].ch[c]==q;p=t[p].fa)    t[p].ch[c]=nq;

}

void build()

{

    for(int i=;i<=poi;i++)    add(t[i].fa,i);

}

void dfs(int x)

{

    for(int i=in[x];i;i=e[i].lt)

        dfs(e[i].to),t[x].sz+=t[e[i].to].sz;

    if(t[x].sz!=)    ans=max(ans,t[x].len*t[x].sz);

}

int main()

{

    scanf("%s",ch+); n=strlen(ch+); rt=lt=poi=;

    for(int i=;i<=n;i++)    insert(id(ch[i]));

    build(); dfs(); printf("%d\n",ans);

    return ;

}

✔线性规划

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<ctime>

#define db long double

#define ll long long

#define inf 20021225

#define eps 1e-10

using namespace std;

db a[][],ans[]; int id[],n,m;

void pivot(int x,int y)

{

    swap(id[n+x],id[y]);

    db w=1.0/a[x][y]; a[x][y]=1.0;

    for(int i=;i<=n;i++)    a[x][i]*=w;

    for(int i=;i<=m;i++)

    {

        if(i==x || abs(a[i][y])<eps)    continue;

        w=a[i][y]; a[i][y]=0.0;

        for(int j=;j<=n;j++)

            a[i][j]-=a[x][j]*w;

    }

}

bool prework()

{

    while()

    {

        int x=,y=;

        for(int i=;i<=m;i++)    if(a[i][]<-eps && (!x||rand()&))    x=i;

        if(!x)    return true;

        for(int i=;i<=n;i++)    if(a[x][i]<-eps && (!y||rand()&))    y=i;

        if(!y){printf("Infeasible\n");return false;}

        pivot(x,y);

    }

}

bool simplex()

{

    while()

    {

        int x=,y=; db mn=1e15;

        for(int i=;i<=n;i++)    if(a[][i]>eps){y=i;break;}

        if(!y)    return true;

        for(int i=;i<=m;i++)

            if(a[i][y]>eps && a[i][]/a[i][y]<mn)

                x=i,mn=a[i][]/a[i][y];

        if(!x){printf("Unbounded\n");return false;}

        pivot(x,y);

    }

}

int main()

{

    srand(time()); int t;

    scanf("%d%d%d",&n,&m,&t);

    for(int i=;i<=n;i++)    scanf("%Lf",&a[][i]),id[i]=i;

    for(int i=;i<=m;i++)

    {

        for(int j=;j<=n;j++)    scanf("%Lf",&a[i][j]);

        scanf("%Lf",&a[i][]);

    }

    if(prework()&&simplex())

    {

        printf("%.8Lf\n",-a[][]);

        if(t)

        {

            for(int i=;i<=m;i++)    ans[id[n+i]]=a[i][];

            for(int i=;i<=n;i++)    printf("%.8Lf ",ans[i]);

        }

    }

    return ;

}

回文自动机

✔半平面交

✔旋转卡壳

✔欧拉回路

✔整体二分

✔可持久并查集

✔kruskal重构树

✔点分治/动态点分治

✔凸优化/斜率优化

上下界网络流

✔差分约束

✔LCT

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 20021225

#define N 300100

#define ls(x) t[x].son[0]

#define rs(x) t[x].son[1]

#define fa(x) t[x].fa

#define isroot(x) (rs(fa(x))!=x && ls(fa(x))!=x)

using namespace std;

struct node{int fa,son[],val,sum; bool rev;}t[N];

void pushup(int x){t[x].sum=t[ls(x)].sum^t[rs(x)].sum^t[x].val;}

void pushdown(int x)

{

    if(t[x].rev)

    {

        if(ls(x))    t[ls(x)].rev^=;

        if(rs(x))    t[rs(x)].rev^=;

        swap(ls(x),rs(x)); t[x].rev=;

    }

}

void rotate(int x)

{

    if(!x || isroot(x))    return;

    int f=fa(x),gf=fa(f);

    int k=rs(f)==x,p=k^;

    if(!isroot(f))    t[gf].son[rs(gf)==f]=x;

    t[x].fa=gf; t[f].fa=x;

    if(t[x].son[p])    t[t[x].son[p]].fa=f;

    t[f].son[k]=t[x].son[p]; t[x].son[p]=f;

    pushup(f); pushup(x);

}

void push(int x){if(!isroot(x))    push(fa(x));pushdown(x);}

void splay(int x)

{

    push(x);

    while(!isroot(x))

    {

        int f=fa(x),gf=fa(f);

        if(!isroot(f))    (rs(gf)==f)^(rs(f)==x)?rotate(x):rotate(f);

        rotate(x);

    }

}

void access(int x)

{

    int y=;

    do

    {

        splay(x);

        t[x].son[]=y;

        pushup(x);

        y=x; x=t[x].fa;

    }while(x);

}

void makeroot(int x)

{

    access(x); splay(x); t[x].rev=;

}

int findroot(int x)

{

    access(x); splay(x);

    while(ls(x))    x=ls(x);

    return x;

}

void link(int x,int y)

{

    makeroot(x);

    if(findroot(y)==x)    return;

    t[x].fa=y;

}

void cut(int x,int y)

{

    makeroot(x);

    if(findroot(y)==x && t[x].fa==y && !t[x].son[])

    {

        t[x].fa=t[y].son[]=; pushup(y);

    }

}

void modify(int x,int val)

{

    splay(x);

    t[x].val=val;

    pushup(x);

}

int query(int x,int y)

{

    makeroot(x);access(y);splay(y);return t[y].sum;

}

int main()

{

    int n,m,i,x,y,opt;

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++)    scanf("%d",&t[i].val);

    for(i=;i<=m;i++)

    {

        scanf("%d%d%d",&opt,&x,&y);

        if(opt==)    printf("%d\n",query(x,y));

        if(opt==)    link(x,y);

        if(opt==)    cut(x,y);

        if(opt==)    modify(x,y);

    }

    return ;

}

莫比乌斯反演

积性函数相关

✔Polya

线段树合并

✔插头dp

✔虚树

✔CRT/EXCRT

//Love and Freedom.

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define ldb long double

#define inf 20021225

#define N 100010

using namespace std;

ll ksc(ll a,ll b,ll md)

{

    ll c=(a*b-(ll)((ldb)a/md*b+0.5)*md);

    return c<?c+md:c;

}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(!b){x=;y=;return a;}

    ll g=exgcd(b,a%b,x,y);// printf("QAQ");

    ll k=x; x=y; y=k-a/b*y; return g;

}

ll p[N],w[N]; int n;

ll excrt()

{

    ll x=w[],P=p[],t,s;

    for(int i=;i<=n;i++)

    {

        ll k=((w[i]-x)%p[i]+p[i])%p[i];

        ll g=exgcd(P,p[i],t,s); ll bs=p[i]/g;

        if(k%g!=)    return -;

        t=ksc(t,k/g,bs); x+=t*P; P*=bs;

        x=(x%P+P)%P;

    }

    return x;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)    scanf("%lld%lld",&p[i],&w[i]);

    printf("%lld\n",excrt());

    return ;

}

巴特西

SDOI前的小计划

最新文章

热门文章