曹冲养猪（中国剩余定理模板题）

本文主要是介绍曹冲养猪（中国剩余定理模板题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题意

有若干对数据：ai , bi 代表n%ai=bi , 求n的最小数目，其中ai之间两两互质

---

思路

中国剩余定理模板题
对于n个互质的数mi，存在x使得任意n个正整数ai满足：
x≡a1(mod m1)
x≡a2(mod m2)
x≡a3(mod m3)
…
x≡ai(mod mi)

方程组的解为：x=a1 M1 x1 + a2 M2 x2 + … + ai Mi xi (在模M下有唯一解)

其中：
M=m1*m2…mi
Mi=M/mi
xi的值为：Mi xi ≡ 1 ( mod mi )的解xi，可用扩展欧几里得求出（即求解：Mi * xi + yi * mi = 1)

注意M是累乘的积，数据范围开LL

---

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
ll m[15],a[15];
ll x,y,g,n;
void exgcd(ll a,ll b)
{if(b==0){x=1,y=0,g=a;return;}exgcd(b,a%b);ll t=x;x=y;y=t-a/b*y;
}
void Intchina()
{ll M=1,Mi,ans=0;for(int i=0;i<n;i++) M*=m[i];for(int i=0;i<n;i++){Mi=M/m[i];exgcd(Mi,m[i]);ans=(ans+Mi*a[i]*x)%M;}printf("%lld\n",(ans+M)%M);return;
}
int main()
{scanf("%lld",&n);for(int i=0;i<n;i++)scanf("%lld%lld",&m[i],&a[i]);Intchina();return 0;
}

这篇关于曹冲养猪（中国剩余定理模板题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---