目的 アルファベットを一文字ずつ順に出力する。 コード 小文字 for (int i = 0; i <= ('z' - 'a'); i++) { char tmp=(char)('a' + i); } 大文字 for (int i = 0; i <= ('Z' - 'A'); i++) { char tmp=(char)('A' + i); } コードテスト #include <bits/stdc++.h> using names</bits/stdc++.h>…

目的 要素xと要素yが同じグループに属するかどうかを判定するためのデータ構造。 また、要素xと要素yそれぞれが属するグループを併合することが可能。 関数 root(x)：xの根を返す。 unite(x,y)：xとyを併合する。 same(x,y)：xとyが同じ木に属するならtrue,…

目的 stringの文字列を大文字または小文字に揃える。 コード string s; transform(s.begin(), s.end(), s.begin(), ::toupper);//大文字に変換 transform(s.begin(), s.end(), s.begin(), ::tolower);//小文字に変換 コードテスト #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

目的 環境変えても貼り付けるだけにしたい コード #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll, ll> p_ll; typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i) #define ture ture #define flase false #de</pair<ll,></pair<ll,></ll,></bits/stdc++.h>…

目的 mod m の世界において、aに対する逆元a-1を計算する。 これを利用することで、剰余同士の割り算が可能になる。 制約 aとmは互いに素である。 オーダー コード //拡張ユークリッド互除法 long long int ext_gcd(long long int a, long long int b, long …

目的 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; …