異端開発室

アルゴリズム最適化の基本概念 競技プログラミングにおいて、問題の制約を満たすためには、単純な全探索から数学的な性質や効率的なデータ構造への転換が不可欠です。本記事では、約数とオイラー関数を用いた数論的問題、最長増加部分列（LIS）の個数計算におけるセグメント木の応用、そしてフィボナッチ数列に基づく木構造の動的計画法（DP）について、その数学的背景と計 ...

素因数分解 void factorize(int n, vector<int>& primes) { for (int d = 2; 1LL * d * d <= n; ++d) { if (n % d == 0) { primes.push_back(d); while (n % d == 0) n /= d; } } if (n > 1) primes.push_back(n); } ユークリッドの互除法による GCD / LCM int gcd(int x, int y) { return y ? g ...

問題の定式化 C 言語様の_for_ループ構造において、制御変数が k ビットの符号なし整数型として振る舞う場合の実行回数を求める問題について解説します。具体的なループ構造は以下のように定義されます。 for (variable = A; variable != B; variable += C) statement; このループは、変数 variable を初期値 A で開始し、B に一致するまでステートメントを実行し、毎 ...

問題 1：数論的和の計算 この問題では、大きな指数を持つべき乗の和を特定の素数で割った余りを求める必要がある。 naive な快速幂を用いた計算では $O(\sqrt{m} \cdot \log n)$ となり、制限時間を超えてしまう。ここで、法となる数が小さくかつ素数であることに注目する。 フェルマの小定理より、指数部分は法 $p$ に対して $p-1$ で割った余りとして扱ってよい。これに ...