poj2891 Strange Way to Expres Integers

墨蓝 2021-10-25 13:44 223阅读 0赞

题目链接；https://www.acwing.com/problem/content/description/206/  
题目描述：  
给定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≤231−1  
,  
0≤mi<ai  
1≤n≤25

输入样例：

2  
8 7  
11 9

输出样例：

分析：  
这看似中国剩余定理，实则却不满足中国剩余定理。  
我们可以先考虑第一个和第二个式子，我们把满足这两个式子的解先求出来。通过归纳，即可得正确答案。  
看到一篇初中生的巨巨博客，讲的很好。故我在此不做过多表述了。  
参考博客：https://www.acwing.com/solution/acwing/content/3539/\#comment\_3155

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll n,a1,m1;
    
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
        if(b == 0)
        {
            x = 1; y = 0; return a;
        }
        ll d = exgcd(b,a%b,x,y);
        ll z = x; x = y; y = z - y * (a / b);
        return d;
    }
    int main()
    {
        scanf("%lld",&n);  n -= 1;
        scanf("%lld%lld",&a1,&m1);
        ll k1,k2;
        while(n --)
        {
            ll a2,m2;
            scanf("%lld%lld",&a2,&m2);
            ll c = m2 - m1;
            ll d = exgcd(a1,-a2,k1,k2);
            if(c % d)
            {
                printf("-1\n"); return 0;
            }
            k1 *= c / d;
            k1 = (k1 % abs(a2 / d) + abs(a2 / d)) % abs(a2 / d);
            m1 = k1 * a1 + m1; a1 = abs(a1 * a2 / d);
        }
        printf("%lld\n",m1);
    }