互质
ll m[N],p[N];//p是质数,m是余数 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非互质
#include//*m模数 *a余数 #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; } 另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享文章:中国剩余定理-创新互联
标题来源:http://bjjierui.cn/article/ddjohh.html