exCRT & 骆克强乘法

exCRT & 骆克强乘法

只是丢两个板子啦。

exCRT的做法就是每次拿两个方程合并成一个,合并的过程推下式子就是个 exgcd。具体可以在 zjk 的 ptt 里面找到。

先放个$O(1)$慢速乘

1
ll mul( ll a , ll b , ll p ) { a %= p , b %= p; return ( (a * b - (ll)( (ll)( (long double)a / p * b + 0.5 ) * p )) % p + p ) % p; }

然后一个 exgcd

1
2
3
4
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 );
}

最后是 excrt

Luogu 板子题和 PTT 上的 ab 居然是反着的。。。毒瘤

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 100006
typedef long long ll;
ll mul( ll a , ll b , ll p ) { a %= p , b %= p; return ( (a * b - (ll)( (ll)( (long double)a / p * b + 0.5 ) * p )) % p + p ) % p; }
int n;
ll A[MAXN] , B[MAXN];
ll gcd( int a , int b ) { return b ? a : gcd( b , a % b ); }
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 );
}
bool crt( ll& a1 , ll a2 , ll& b1 , ll b2 ) {
ll d = a2 - a1;
ll g , k1 , k2;
exgcd( b1 , b2 , g , k1 , k2 );
if( d % g ) return 0;
else {
ll r = b2 / g;
k1 = mul( k1 , d / g , r );
a1 = k1 * b1 + a1;
b1 = ( b1 * r );
return 1;
}
}
ll excrt( ) {
ll a1 = A[0] , b1 = B[0] , a2 , b2;
for( int i = 1 ; i < n ; ++ i ) {
a2 = A[i] , b2 = B[i];
if( !crt( a1 , a2 , b1 , b2 ) ) return -1;
}
return a1;
}


int main() {
cin >> n;
for( int i = 0 ; i < n ; ++ i ) scanf("%lld%lld",&B[i],&A[i]);
cout << excrt( ) << endl;
}

文章作者: yijan
文章链接: https://yijan.co/old64/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog