中國(guó)剩余定理

互質(zhì)

長(zhǎng)春網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),長(zhǎng)春網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為長(zhǎng)春成百上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站建設(shè)要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的長(zhǎng)春做網(wǎng)站的公司定做！

 ll m[N],p[N];//p是質(zhì)數(shù)，m是余數(shù)
ll Exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll d=Exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return d;
}
ll Crt(ll *m,ll *p,int l)
{
    ll res=0,n=1,x,y;
    for(int i=0;i<l;i++)
        n*=p[i];
    for(int i=0;i<l;i++)
    {
        ll t=n/p[i];
        ll d=Exgcd(t,p[i],x,y);
        res=(res+m[i]*t%n*x%n)%n;
    }
    return (res%n+n)%n;
}

非互質(zhì)

#include<cstdio>//*m模數(shù) *a余數(shù)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;y=0;return ;
    }
    exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;y=temp-(a/b)*y;
}
ll inv(ll a,ll b)
{
    ll d=__gcd(a,b);
    if(d!=1)return -1;
    ll x,y;
    exgcd(a,b,x,y);
    return (x%b+b)%b;
}
bool merge(ll a1,ll m1,ll a2,ll m2,ll &a3,ll &m3)
{
    ll d=__gcd(m1,m2);
    ll c=a2-a1;
    if(c%d)return false;
    c=(c%m2+m2)%m2;
    m1/=d;m2/=d;c/=d;
    c*=inv(m1,m2);c%=m2;
    c*=m1*d;
    c+=a1;m3=m1*m2*d;
    a3=(c%m3+m3)%m3;
    return true;
}
ll CRT(ll *a,ll *m,ll n)
{
    ll a1=a[1],m1=m[1];
    for(ll i=2;i<=n;i++)
    {
        ll a2=a[i],m2=m[i];
        ll m3,a3;
        if(!merge(a1,m1,a2,m2,a3,m3))
        return -1;
        a1=a3;m1=m3;
    }
    return (a1%m1+m1)%m1;
}

分享題目：中國(guó)剩余定理
文章網(wǎng)址：http://muchs.cn/article30/ispiso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、網(wǎng)站改版、關(guān)鍵詞優(yōu)化、域名注冊(cè)、做網(wǎng)站、微信公眾號(hào)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)