1018 一个小问题 扩展中国剩余定理


链接: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

(0)
上一篇 2022年7月28日
下一篇 2022年7月28日

相关推荐

发表回复

登录后才能评论