算術の基本定理 - 素因数分解の理論と実装
算術の基本定理
素数と素因数の基礎概念
算術の基本定理を理解するにあたり、まず基本となる用語を整理しておこう。素数とは、2以上の自然数のうち、1とその数自身以外では割り切れない数を指す。代表的な素数としては2、3、5、7、11などが挙げられる。一方、素因数とは、ある整数を構成する素数のことを意味する。例えば、12という数は2×2×3という積で表わされるが、この ...
6月28日 20:09 投稿
数論の基礎と応用
因数に関する考察
1からnまでのすべての数の因数の総数はO(n log n)である。
1からnまでの素数の個数はO(n / log n)である。
伯トラン・チェビシェフの定理：n ≥ 1のとき、nと2nの間に少なくとも1つの素数がある。
直角三角形の辺の長さの一般式：a = w * 2uv, b = w * (u^2 - v^2), c = w * (u^2 + v^2)、ここでu, v, wは正の整数。
問題
Common Divisors: a_1, a_2, ...
6月22日 20:48 投稿
2024年ICPCヨーロッパ大会最終問題解説
A. Hitoshizuku
貪欲法で解きます。
右端点でソートした後、マッチングされていない点に対して、各右端点以下の点を管理し、その端点が管理されている集合の中で右端点が最も小さい2点とマッチングします。
最適性の証明は調整法によるそうです。
コード例
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using name ...
6月21日 19:26 投稿
オイラーのトーシェント関数と線形ふるい法による計算
例えば、6のオイラーのトーシェント関数を求める場合：6=2×3なので、そのトーシェント関数は6×(2-1)/2×(3-1)/3となります。
原理：1~NのうちNと互いに素な数の個数は、NからNと互いに素でない数を引いたものに等しくなります。Nと互いに素でない数はNの因数の倍数によってふるい落とされますが、一部の数は複数の因数によって複数回ふるい落とされるため、因数の積の倍数を ...
6月15日 22:32 投稿
アルゴリズムとデータ構造8 - 線形篩による一般乗法関数の計算
概要
競技プログラミングの問題を解く中で、線形篩を用いた一般乗法関数の計算方法を学んだので、その説明を行う。
前提知識
乗法的関数：任意の互いに素な整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
完全乗法的関数：任意の整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
線形篩：O(n)でn以下の素数を列挙するアルゴリズム。
適用範囲
任意の素数pに対して、f(p)およ ...
6月10日 19:05 投稿
藍橋杯2021年省赛B組 C/C++ 問題解説
問題A：空間計算
メモリ空間の計算問題。256MBをバイト単位で表現し、各データが32ビット（4バイト）の場合の要素数を求める。
計算式：256 × 1024 × 1024 × 8 ÷ 32 = 67108864
問題B：カードの数字
0から9までの数字カードが各2021枚ずつある。1から順に数字を書いていくとき、何まで書けるかを求める問題。
#include <iostream>
using namespace std;
int main( ...
6月5日 23:06 投稿
min25筛と洲閣筛
min25筛
ある積性関数 f(x) が与えられ、f(p) が素数 p に関する多項式で、かつ f(pk) が高速に計算できる場合、sumi=1n f(i) を求める。
例：n = 1010 に対して sumi=1n σ0(ik) を求める。
ステップ1：素数の積性関数の前処理和
1 から n までの素数の個数を求める。
f(n, m) を、2 から n までの数のうち、素数であるか、または最小の素因数が p1, ..., pm (pi は i 番 ...
6月1日 21:05 投稿
線形ふるい法による素数、オイラー関数、メビウス関数の高速計算
線形ふるい法 (Linear Sieve)
線形ふるい法は、ある範囲内の素数を効率的に求めるアルゴリズムです。このアルゴリズムの時間計算量はO(n)であり、各合成数が一度だけふるい落とされることを保証します。本稿では、線形ふるい法を用いて素数、オイラー関数、メビウス関数を計算する方法を解説します。
1. 素数の線形ふるい
素数の線形ふるいは、指定された上限Nまでのすべ ...
5月18日 22:09 投稿