首页 > 其他 > 详细

中国剩余定理 快速乘 洛谷P3868

时间:2019-08-21 09:44:45      阅读:114      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.luogu.org/problem/P3868

题意:就是裸的中国剩余定理,为了防止TLE要加上快速乘,但是要注意a[i]可能为负数,故需要对a[i]做处理:a[i]=(a[i]%b[i]+b[i])%b[i])

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long lt;

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<0||ss>9){if(ss==-)f=-1;ss=getchar();}
    while(ss>=0&&ss<=9){x=x*10+ss-0;ss=getchar();}
    return x*f;
}

int k;
lt a[20],b[20];

lt qmul(lt a,lt b,lt mod)
{
    lt ans=0;
    while(b>0)
    {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

void exgcd(lt a,lt b,lt &x,lt &y)
{
    if(b==0){ x=1; y=0; return;}
    exgcd(b,a%b,x,y);
    int tp=x;
    x=y; y=tp-a/b*y;
}

lt china()
{
    lt ans=0,lcm=1,x,y;
    for(int i=1;i<=k;++i) lcm*=b[i];
    for(int i=1;i<=k;++i)
    {
        lt tp=lcm/b[i];
        exgcd(tp,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];
        ans=(ans+qmul(qmul(tp,x,lcm),a[i],lcm))%lcm;//记得快速乘
    }
    return (ans+lcm)%lcm;
}

int main()
{
    k=read();
    for(int i=1;i<=k;++i) a[i]=read();
    for(int i=1;i<=k;++i) b[i]=read();
    for(int i=1;i<=k;i++) a[i]=(a[i]%b[i]+b[i])%b[i];
    cout<<china();
    return 0;
    //niiick
}

 

中国剩余定理 快速乘 洛谷P3868

原文:https://www.cnblogs.com/qingjiuling/p/11386843.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!