题解 P1495 【曹冲养猪】

灵乌路空

2019-05-20 20:27:28

Solution

无良宣传一下博客wwwwww [文章列表 - 核融合炉心 - 洛谷博客](https://www.luogu.org/blog/koishikoishi/) - ### 分析题意: 现有两组数字,每组 $k$ 个, 第一组中的数字分别为:$a_1,a_2,...,a_k$ 表示, 第二组中的数字分别用$b_1,b_2, ... ,b_k$表示。 第二组中的数字$\underline\text{两两互质}$。 求最小的非负整数 $n$ , $\underline{\text{满足对于任意的}i,n - a_i \text{ 能被 } b_i \text{ 整除}}$。 根据题意 , 题干可以转化为: - ##### 要解如下的同余方程组 : $\begin{cases}x \equiv a_1\pmod {b_1}\\x \equiv a_2\pmod {b_2}\\......\\x \equiv a_n\pmod {b_n}\\\end{cases}$ 因为 $bi$ 之间 **两两互质**,所以可以用 **中国剩余定理** 求解 但是 中国剩余定理 适用范围太小, 这里介绍用 **扩展中国剩余定理** 求解。 ## 求解同余方程组 (扩展中国剩余定理) 一道模板题: [P4777 【模板】扩展中国剩余定理(EXCRT)](https://www.luogu.org/problemnew/show/P4777) - ### 要解如下的同余方程组 : $\begin{cases}x \equiv a_1\pmod {b_1}\\x \equiv a_2\pmod {b_2}\\......\\x \equiv a_n\pmod {b_n}\\\end{cases}$ 其中 , $a_i,b_i$为非负整数 , $b_1,b_2,...,b_n$ 不一定互质 - ### 求解: 假设已经求出了前 $k-1$ 个方程的解 $x_{k-1}$ 设 $M=LCM_{i=1}^{k-1} bi$ , 即 $M$ 为前 $k-1$ 个模数 $b$ 的最小公倍数 **则 :** 对于前 $k-1$个方程, 都满足$x_{k-1}+tM\equiv a_i\pmod {b_i}\ \ (t\in Z)$ 即 : 前 $k-1$ 个方程 , 通解为 $x_{k-1}+tM\ \ (t\in Z)$ 欲求得第 $k$ 个方程的解 , 并且将求得的解 , 也满足前 $k-1$ 个方程 **则 :** 需要使第 $k$ 个方程的解 , 为前 $k-1$ 的方程的通解的同时 , 也满足第 $k$ 个方程的条件 。 设 : 第$k$ 个方程的解 $x_k = x_{k-1}+tM\ \ (t\in Z)$ 将此解代入第 $k$ 个方程中 , 可得 : $x_{k-1}+tM\equiv a_k\pmod{b_k}$ 即 : $tM\equiv a_k-x_{k-1}\pmod{b_k}$ 其中 : $M,a_k,x_{k-1},b_k$ 都是已知的 。 使用 $exgcd$ 解出此同余方程 , 可以得到 $t$ 的值 。 将 $t$ 的值代回 $x_k = x_{k-1}+tM\ \ (t\in Z)$ ,就可得到$x_k$的值 进行 $k$ 次上述操作后 ,便可得到 方程组的解 。 - #### 附本题AC代码: ```cpp //扩展中国剩余定理模板题目 //详见注释 #include<cstdio> using namespace std; typedef long long ll; ll n; ll a[100010],b[100010]; ll mul(ll A,ll B,ll mod) //快速乘取余 模板 { ll ans=0; while(B>0) { if(B & 1) ans=(ans+A%mod)%mod; A=(A+A)%mod; B>>=1; } return ans; } ll exgcd(ll A,ll B,ll &x,ll &y) //扩展欧几里得 模板 { if(!B) { x=1,y=0; return A; } ll d=exgcd(B,A%B,x,y); ll tmp=x; x=y , y=tmp-A/B*y; return d; } ll lcm(ll A,ll B) //求最小公倍数 { ll xxx,yyy; ll g=exgcd(A,B,xxx,yyy); return (A/g*B); } ll excrt() //重点:求解同余方程组 { ll x,y; ll M=b[1],ans=a[1]; //赋初值 //M为前k-1个数的最小公倍数,ans为前k-1个方程的通解 for(int i=2;i<=n;i++) { ll A=M,B=b[i]; ll C=(a[i]-ans%B+B)%B; //代表同余方程 ax≡c(mod b) 中a,b,c ll g=exgcd(A,B,x,y); //求得A,B的最大公约数,与同余方程ax≡gcd(a,b)(mod b)的解, if(C%g) return -1; //无解的情况 x=mul(x,C/g,B); //求得x的值,x即t ans+=x*M; //获得前k个方程的通解 M=lcm(M,B); //更改M的值 ans=(ans%M+M)%M; } return ans; } int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&b[i],&a[i]); ll ans=excrt(); printf("%lld",ans); } ```