본문 바로가기

PS

 (11)
밀러라빈 using ll = long long;inline ll multiply(ll a, ll b, ll mod) { return __int128(a) * b % mod; }ll power(ll a, ll n, ll mod) { //a ^ n % mod ll res = 1; while (n) { if (n & 1) res = multiply(res, a, mod); a = multiply(a, a, mod); n >>= 1; } return res;}bool isPrime(ll n) { if (n >= 1, ++r; auto check = [&](ll a) { ll remain = power(a, d, n); if (..
Deterministic Verification of Integer Matrix Multiplication in Quadratic Time 세 개의 $n \times n$ 크기의 정수 행렬 $A, B, C$에 대해 $AB == C$인지 $O(N^2)$에 판별하는 알고리즘을 알아보자.PS에서 보통 사용되는 $O(KN^2)$의 Freivalds' algorithm을 개선한 버전으로 생각할 수도 있지만, 이 알고리즘은 PS에선 쓰이지 않는다. 먼저, naive하게 $AB$를 계산하고 $C$와 비교하는 알고리즘의 시간복잡도는 $O(N^3)$이다. $AB$의 계산에서 $n \times n$ 크기의 두 행렬을 곱해야 하므로 $O(N^3)$의 계산이 필요하고, 계산된 결과가 $C$와 일치하는지 확인하는 데에 $O(N^2)$의 비교가 필요하기 때문이다. 조금 더 효율적인 방법이 없을까? $AB=C$라면 임의의 $n \times 1$ 열벡터 $x$에 대..
간단한 exgcd 1. exgcdtuple extendedGCD(ll a, ll b) { // ax + by = gcd(a, b) if (b == 0) return {1, 0, a}; auto [x2, y2, g] = extendedGCD(b, a % b); return {y2, x2 - (a / b) * y2, g};}베주항등식 $ax_1 + by_1 = g$ 는 항상 해 존재$let)~ a=bk+r$$(bk + r)x_1 + by_1 = g$$b(kx_1+y_1) + rx_1 = g$$let)~ x_2 = kx_1+y_1, y_2=x_1$$\therefore x_1=y_2, y_1 = x_2-ky_2$2. modular inversell modInverse(ll a, ll b) { // a^-1 mod..

티스토리툴바