caioj 1155 同余方程组(模版)

第一步，和同余方程一样，转化一下

$P=b1(mod m1) \rightarrow m1*x+b1 = P$

$P=b2(mod m2) \rightarrow m2*y+b2 = P$

两式相减得

$m1 * y - m2 * y = b2 - b1$

这就转化为了求不定方程，用exgcd

求出x，要化成最小正整数解，避免溢出

然后可以求出P出来。

这个时候要把前两个式子转化成一个式子

设求出来的是P’

则有 $P=P'(modlcm(m1, m2))$

这个就转化成了新的m1和b1

然后就一直求下去即可

最终b1就是答案

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

void exgcd(ll a, ll b, ll& d, ll& x, ll& y)

{

	if(!b) { d = a; x = 1; y = 0; return; }

	else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }

}

int main()

{

	ll n, b1, m1, b2, m2;

	scanf("%lld%lld%lld", &n, &b1, &m1);

	bool ok = true;

	REP(i, 1, n)

	{

		scanf("%lld%lld", &b2, &m2);

		ll A, B, K, x, y, d;

		A = m1, B = m2, K = b2 - b1;

		exgcd(A, B, d, x, y);	

		if(K % d != 0) ok = false;

		x *= K / d; int mod = B / d;

		x = (x % mod + mod) % mod;

		b1 = m1 * x + b1; //这里顺序要注意

		m1 = m1 / d * m2;

	} 

	if(!ok) puts("no solution!");

	else printf("%lld\n", b1);

	return 0;

}

巴特西

caioj 1155 同余方程组(模版)

最新文章

热门文章