目的 1～Nまでの素数を判定し、vector型に収納する。 素数であれば1を、合成数であれば0を返す。 オーダー O(N log logN) コード vector<bool> prime_table(int n) { vector<bool> prime(n + 1, true); if (n >= 0) prime[0] = false; if (n >= 1) prime[1] = false; for</bool></bool>…

目的 約数をvectorに保存する。 制約 コード vector<long long> divisor(long long n) { vector<long long> ret; for (long long i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(begin(ret), end(ret)); return (</long></long>…

目的 素数であればtrue、そうでなればfalseを返す。 オーダー O(√N) コード bool is_prime(long long x) { for(long long i = 2; i * i <= x; i++) { if(x % i == 0) return false; } return true; } 出典 ei1333.github.io

目的 累乗を素数で割った際の剰余を求める。 コード long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } コードテスト #include <iostream></iostream>…

目的 素因数分解をする。 オーダー O(√N) コード vector<pair<long long, long long>> prime_factorize(long long N) { vector<pair<long long, long long>> res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++e</pair<long></pair<long>…

目次 nCk n～107程度 nCk n固定,k～105程度 nCk n～106程度 ACL使用ver 1. nCk n～107程度 目的 二項係数nCkを素数pで割った際の剰余nCk mod pを求める。 制約 p：素数 1≦k≦n≦107 n

目的 最大公約数と最小公倍数を求める。 コード long long int gcd(long long int a, long long int b) { return b ? gcd(b, a % b) : a; } //AとBの最大公約数(A>0, B>0) long long int lcm(long long int a, long long int b){ return a / gcd(a, b) * b; …