链接:https://ac.nowcoder.com/acm/problem/15068
来源:牛客网
题目描述
uu遇到了一个小问题,可是他不想答。你能替他解决这个问题吗?
问题:给你k对a和r是否存在一个正整数x使每队a和r都满足:x mod a=r,求最小正解x或无解。
输入描述:
第一行是正整数k(k<=100000)
接下来k行,每行有俩个正整数a,r(100000>a>r>=0)
输出描述:
在每个测试用例输出非负整数m,占一行。
如果有多个可能的值,输出最小的值。
如果没有可能的值,则输出-1。
示例1
输入
2 8 7 11 9
输出
31
分析
由于模数不互质,所以要用扩展中国剩余定理。
要注意让(m2 - m1) / d,让k1 / d可能会损失
思想:
由前两项得到方程:
x = k1 * a1 + m1;
x = k2 * a2 + m2;
消去x 得到方程:k1 * a1 – k2 * a2 = (m2 – m1)
通过扩展欧几里得算出:k1′ * a1 – k2′ * a2 = (a1,a2)
进而算出k1 = k1′ * a2 / (a1,a2) ;
构造新的 x = k1 * a1 + m1
x=(k1+k∗a2/d)∗a1+m1x
=k1∗a1+m1+k∗a2∗a1/d
=k1∗a1+m1+k∗lcm(a1,a2)
等价替换得到:
新的a1 = abs(lcm(a1,a2))
新的m1 = k1 * a1 + m1;
int k; #define int long long int exgcd(int a,int b,int& x,int& y) { if(!b) { x = 1,y = 0; return a; } int d = exgcd(b,a%b,y,x); y = y - a / b * x; return d; } inline int mod(int a,int b) { return (a % b + b) % b; } int EXCRT() { int a1,m1; cin>>a1>>m1; fo(i,2,k) { int a2,m2;cin>>a2>>m2; int k1,k2,d = exgcd(a1,-a2,k1,k2); if((m2 - m1) % d) {return -1;} k1 = mod(k1 * (m2 - m1) / d,abs(a2 / d));//要注意让(m2 - m1) / d,让k1 / d可能会损失 m1 = k1 * a1 + m1; a1 = abs(a1 / d * a2); } return mod(m1,a1); } signed main() { cin>>k; cout<<CRT()<<endl; }
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/277465.html