【競プロ整数ライブラリ】蟻本 2-6章 まとめ - ゆらのふなびと蟻本2-6章を読んで素数・約数系のライブラリ的なものができたのでまとめておきます。説明は全部蟻本にあるぞい。 【なかみ】 gcd(a, b): aとbの最大公約数 lcm(a, b): aとbの最小公倍数 extgcd(a, b, &x, &y): ax + by = gcd(a,b) の解(x,y)を得る(拡張ユーグリッド互除法) is_prime(n): 素数判定 vector divisor(n): 約数のvectorを返す map<int, int> prime_factor(n): 素因数分解(25*32 = {2:5, 3:2}みたいな感じで返ってくる) sieve(n): エラトステネスのふるい(nまでの素数表を作る) count_prime(a, b): [a, b)内の素数の個数を返す mod_pow(x, n, mod): xn % modを高速演算 getFib(k)
