caioj 1154 同余方程（模版）

求x的最小正整数解，使得ax=b(mod m)

那么显然ax - b = m * y

ax - my = b

那么就套入Ax+By = K的不定方程中，然后用exgcd求解即可

但这道题求最大正整数解，对于一组解，有这样一个推论

x = x０ +ｋ＊（ｂ／ｇｃｄ（ａ，ｂ））　

y = ｙ０－ｋ＊（ａ／ｇｃｄ（ａ，ｂ））　

k为任意正整数可以带入方程中算一下，依然满足方程。

那么也就是说x的变化幅度为b / ｇｃｄ（ａ，ｂ）

令d = ｇｃｄ（ａ，ｂ）， B = b

那么最小正整数解就是 (x * (K / d)) % (B/d) + (B/d)) % (B/d)

x * (K / d)是一个解，然后模掉(B/d)，也就是变成和0最近的解

如果是负数，再加上一个(B/d)就整数，然后再模一个(B/d)不会改变值

如果是整数，加上(B/d)再模(B/d)也不会改变值。

所以这样求出来的就是最小正整数解。

最后数论尽量用long long 保险一些，反正一般不开数组，只是开变量，不会耗很多空间，不开白不开。

#include<cstdio>

#include<cctype>

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

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

using namespace std;

typedef long long ll;

void read(ll& x)

{

	int f = 1; x = 0; char ch = getchar();

	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }

	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }

	x *= f;

}

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

{

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

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

}

int main()

{

	ll a, b, m, x, y, d;

	read(a); read(b); read(m);

	ll A = a, B = -m, K = b;

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

	if(K % d != 0) puts("no solution!");

	else printf("%lld", ((x * (K / d)) % (B/d) + (B/d)) % (B/d));

	return 0;

}

巴特西

caioj 1154 同余方程（模版）

最新文章

热门文章