poj2891 Strange Way to Expres Integers-蒲公英云

poj2891 Strange Way to Expres Integers

墨蓝 2021-10-25 13:44 329阅读 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);
}