建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
中國剩余定理-創(chuàng)新互聯(lián)
互質(zhì)
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非互質(zhì)
#include//*m模數(shù) *a余數(shù)
#include
#include
#include
#include
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;
}
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
文章名稱：中國剩余定理-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://fisionsoft.com.cn/article/ddjohh.html
