类欧几里得算法

luckydrawbox · 2024-02-20 20:22:00 · 个人记录

变量

函数

代码

struct leuler{
    struct Node{
        ll f,g,h;
    }res;
    ll n2,n6;
    leuler(){n2=qmi(2,mod-2);n6=qmi(6,mod-2);}
    Node solve(ll a,ll b,ll c,ll n){
        ll ra=a/c%mod,rb=b/c%mod,rn=n%mod;
        if(a==0)return (Node){(rn+1)*rb%mod,(rn+1)*rb%mod*rb%mod,(rn+1)*rn%mod*n2%mod*rb%mod};
        Node x,y;
        if(ra||rb){
            y=solve(a%c,b%c,c,n);
            x.f=(y.f+(rn+1)*rn%mod*n2%mod*ra%mod+(rn+1)*rb%mod)%mod;
            x.g=(2*rb%mod*y.f%mod+y.g+2*ra%mod*y.h%mod
            +rn*(rn+1)%mod*(2*rn%mod+1)%mod*n6%mod*ra%mod*ra%mod
            +rn*(rn+1)%mod*ra%mod*rb%mod+(rn+1)*rb%mod*rb%mod)%mod;
            x.h=(y.h+rn*(rn+1)%mod*(2*rn%mod+1)%mod*n6%mod*ra%mod+(rn+1)*rn%mod*n2%mod*rb%mod)%mod;
            return x;
        }
        ll m=(a*n+b)/c,rm=m%mod;
        y=solve(c,c-b-1,a,m-1);
        x.f=(-y.f+rn*rm%mod+mod)%mod;
        x.g=(-x.f-2*y.f%mod-2*y.h%mod+rn*rm%mod*(rm+1)%mod+3*mod)%mod;
        x.h=(-y.f-y.g+rm*rn%mod*(rn+1)%mod+2*mod)%mod*n2%mod;
        return x;
    }
}eu;