题解 P1495 【曹冲养猪】
灵乌路空
2019-05-20 20:27:28
无良宣传一下博客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);
}
```