0%

扩展欧几里得算法与中国剩余定理

扩展欧几里得算法与中国剩余定理用法。


扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
typedef long long ll;
typedef pair<ll, ll>pll;
pll exgcd(const ll x, const ll y)
{
if(!y)
{
return make_pair(1, 0);
}
pll cur = exgcd(y, x % y);
return make_pair(cur.second, cur.first - (x / y) * cur.second);
}

返回(a, b)代表有这样一数对(a, b)能使 $ax+by=gcd(x, y)$ 。
那么如果$gcd(x, y)=1$,则有a是x在模y下的逆元。 $ax\equiv 1\pmod y$
则 $gcd(x, y)=ax+by$ 。

POJ - 2142
51Nod - 1256


中国剩余定理

中国剩余定理能求解以下问题:
一个数,它模3余2,模5余3,模7余2。这个数最小是多少(或求解在某个区间内的所有符合条件的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ll mod(const ll x, const ll p)
{
return ((x % p) + p) % p;
}

pll crt(const vector<pll> & v)
{
/*
v里每个pll中first为被模数,second为模数
返回数对(a, b)代表这个数模a的值为b
返回(-1, -1)代表不存在
*/
ll a = 1, r = 0;
const int len = v.size();
for(int i = 0; i < len; i++) {
pll cur = exgcd(a, v[i].first);
ll gcd = a * cur.first + v[i].first * cur.second;
if((v[i].second - r) % gcd != 0){
return make_pair(-1, -1);
}
const ll p = v[i].first / gcd;
r += mod(cur.first * ((v[i].second - r) / gcd), p) * a;
a *= p;
}
return make_pair(a, r);
}

POJ - 2891

回到开头