AcWing 204 表达整数的奇怪方式
发布日期:2021-05-28 16:27:06 浏览次数:11 分类:技术文章

本文共 1955 字,大约阅读时间需要 6 分钟。

题目描述:

给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x,满足∀i∈[1,n],x≡mi(mod ai)。

输入格式

第1行包含整数n。第2..n行:每i+1行包含两个整数ai和mi,数之间用空格隔开。

输出格式

输出最小非负整数x,如果x不存在,则输出-1。如果存在x,则数据保证x一定在64位整数范围内。

数据范围

1≤ai≤2^31−1,0≤mi<ai,1≤n≤25

输入样例:

28 711 9

输出样例:

31

分析:

首先,介绍下中国剩余定理。中国剩余定理给出了以下的一元线性同余方程组:

有解的判定条件,并用给出了在有解情况下解的具体形式。中国剩余定理说明:假设m1,m2, ... ,mn,则对任意的整数:a1,a2, ... ,an,方程组S有解,并且通解可以用如下方式构造得到:设是整数m1,m2, ... ,mn的乘积,并设是除了mi以外的n- 1个整数的乘积。

为Mi模mi的乘法逆元,

则方程组S的通解形式为  

在模M的意义下,方程组S只有一个解:

证明:

从假设可知,对任何,由于,所以

这说明存在整数ti使得(变换得tiMi + miy = 1,gcd(mi,MI)=1,故有解)。 也就是说正因为mi,mj互质,才保证了Mi模mi乘法逆元ti的存在。

对于aitiMi而言,0bd162d9f2d3572c46bd64f98913632762d0c3bc.jpg因为Mi是mj的倍数

所以满足:

即x就是方程组S的一个解。

另外,假设x1和x2都是S的解,则

而m1,m2,...,mn两两互质,故x1-x2被mi(i从1到n)整除,即整除x1 - x2.所以S的任意两个解之间必然相差M的整数倍,另一方面,是一个解,同时所有形式为:

的整数也是方程组S的解,所以方程组所有的解的集合就是:

对本题而言,要求x≡mi(mod ai)的最小非负整数解(注意这里ai和mi的含义与上面证明反过来了),由于没有ai,aj互质的条件,故不能保证乘法逆元的存在,所以需要重新求解。由x≡mi(mod ai)推出x = k1a1 + m1,x = k2a2 + m2。故k1a1 - k2a2 = m2 - m1,当gcd(a1,-a2) | m2 - m1时,前两个方程构成的方程组有解。同样,我们用扩展欧几里得算法来求解k1a1 - k2a2 = gcd(a1,-a2) = d的解后,乘上(m2 - m1) / d即可得到k1和k2真正的解。令k1=k1+k∗a2/d,k2=k2+k∗a1/d代入前面的方程发现依旧满足,所以我们得到了k1和k2的一组解,x = (k1+k*a2/d)a1 + m1=k1a1+m1+ka1a2/d=k1a1+m1+klcm(a1,a2),令m = k1a1 + k2a2,a=lcm(a1,a2)就可以得到新的方程x=ka+m了,再与第三个方程继续这样求,直到剩下最后一个方程为止,此时,x=k1a1+m1,x取最小非负整数,则k1应该取k1 % (k*a2/d),此时k1最小,x也最小。

#include 
#include
using namespace std;typedef long long ll;ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){ x = 1,y = 0; return a; } ll d = exgcd(b,a % b,y,x); y -= a / b * x; return d;}int main(){ int n; cin>>n; ll x = 0,m1,a1,m2,a2,k1,k2; cin>>a1>>m1; for(int i = 0;i < n - 1;i++){ cin>>a2>>m2; ll d = exgcd(a1,-a2,k1,k2); if((m2 - m1) % d){ x = -1; break; } k1 *= (m2 - m1) / d; k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d); x = k1 * a1 + m1; ll a = abs(a1 / d * a2); m1 = k1 * a1 + m1; a1 = a; } if(x != -1) x = (x % a1 + a1) % a1; cout<
<

转载地址:https://blog.csdn.net/qq_30277239/article/details/103747201 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 883 高斯消元解线性方程组
下一篇:AcWing 878 线性同余方程

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年02月05日 17时17分22秒