GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
  1. 首页
  2. 数学
  3. 同余
  4. 正文

[Luogu P4777] 【模板】扩展中国剩余定理(EXCRT)

2019年02月25日 318点热度 0人点赞 0条评论

题面

传送门:洛咕


Solution

真*扩展中国剩余定理模板题。我怎么老是在做模板题啊

但是这题与之前不同的是不得不写龟速乘了。

还有两个重点

  • 我们在求LCM的时候,记得先/gcd再去乘另外那个数,直接乘会乘爆的
  • 我们在做龟速乘之前,要保证要乘的两个数>=0,如果<0的话,龟速乘会爆掉的,我们传进去之间记得膜一下

int128:你说啥?这里风太大,我听不见。


Code

//Luogu  P4777 【模板】扩展中国剩余定理(EXCRT)
//Jan,15th,2019
//中国剩余定理
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
    long long x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
long long take(long long A,long long B,long long poi)
{
    if(B==0) return 0;
    long long temp=take(A,B/2,poi)*2%poi;
    if(B%2==1) temp=(temp+A)%poi;
    return temp;
}
long long exgcd(long long A,long long B,long long &x,long long &y)
{
    if(B==0)
    {
        x=1,y=0;
        return A;
    }
    long long t_ans=exgcd(B,A%B,x,y),tx=x;
    x=y,y=tx-(A/B)*y;
    return t_ans;
}

const int N=100000+100;
int n;
long long a[N],p[N];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        p[i]=read(),a[i]=read();

    long long A=a[1],P=p[1];
    for(int i=2;i<=n;i++)
    {
        long long x,y,gcd=exgcd(P,p[i],x,y);
        long long t_P=P,t=p[i]/gcd;
        x=(x%t+t)%t,x=take(x,(((a[i]-A)/gcd)%t+t)%t,t);
        P=P*(p[i]/gcd),A=(A+take(t_P,x,P))%P;
    }

    printf("%lld",(A%P+P)%P);
    return 0;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数学
最后更新:2019年02月25日

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

点赞
< 上一篇
下一篇 >

文章评论

取消回复

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 310
  • 65
  • 80,188
  • 23,375

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号