Integer Divison

有理數就是分數Fraction，而分數又可以想成是商數Quotient。古人認為四則運算時應當使用這個數，這個數很有道理，於是命名為有道理的數。

UVa 11768

Integer Function

https://en.wikipedia.org/wiki/Floor_and_ceiling_functions

Integer Division Series【尚無正式名稱】

中文網路稱作「整除分块」。

時間複雜度O(sqrt(n))。

(floor(n/1) floor(n/2) ... floor(n/n))

void interval(int n) { int l, r; for (l=1; l<=n; l=r+1) { r = n / (n / l); cout << (n / l) << ": [" << l << ',' << r << ']'; } }

floor(n/1) + floor(n/2) + ... + floor(n/n)

int summation(int n) { int sum = 0; int l, r; for (l=1; l<=n; l=r+1) { r = n / (n / l); sum += (r - l + 1) * (n / l); } sum -= (r - n) * (n / l); return sum; }

Grid Coordinate System

https://www.redblobgames.com/grids/hexagons/

UVa 209 10161 808 10182 10595 10964

Ulam Spiral

https://en.wikipedia.org/wiki/Ulam_spiral

https://www.geeksforgeeks.org/find-coordinates-prime-number-prime-spiral/

Pisano Period

http://en.wikipedia.org/wiki/Pisano_period

luogu P3986

Self-referential Formula

http://en.wikipedia.org/wiki/Tupper's_self-referential_formula

Gauss Circle Problem

https://en.wikipedia.org/wiki/Gauss_circle_problem

Pick's Theorem

計算簡單多邊形內部格點數目，多邊形的頂點剛好都在格點上。可以迅速求出簡單多邊形內部會有多少像素，限制是簡單多邊形的頂點必須不偏不倚位於像素上。

簡單多邊形面積 = 簡單多邊形圍住的像素數目 + 簡單多邊形上的像素數目 / 2 - 1

簡單多邊形其中一條邊上面的像素數目，可以利用邊的起點座標與終點座標，以X軸差與Y軸差的最大公因數求得。

計算簡單多邊形內部格點數目，多邊形的頂點在任意位置。【待補文字】

UVa 10088

Farey Sequence

http://www.matrix67.com/blog/archives/2199

Stern-Brocot Tree

UVa 10408 10214

Fraction

GCD Count Function

luogu P2158 P1390

Divisibility

整除性。判斷是否能整除一個數字。

換句話說。判斷一個數字是否是因數，是否可以用於分解。

2: 末位數整除2（個位數是偶數）
3: 所有位數加起來，不斷遞迴
4: 末兩位數整除4
5: 末位數整除5
6: 用2和3來判定

原理是Scaling Method，數字拆開成各種數量級，分別試除、取餘數、相加。

UVa 10212 10929 11879 10211 10127 10275 ICPC 4119

位數判斷

http://www.stat.ualberta.ca/people/schmu/preprints/factorial.pdf

UVa 1185 10061 701 10212 12689

位數循環

UVa 10162

GCD-free Basis

請見專著《Algorithmic Number Theory》。

質因數分解：一個數字分解成質數相乘。時間複雜度類別不明。

互質因數分解：每個數字分解成兩兩互質數字相乘，盡量使用最大公因數。時間複雜度是多項式時間。

tuple(int, set<int>, int) refine(int a, int b) { int d = gcd(a, b); if (d == 1) return {a, {}, b}; auto [l1, s1, r1] = refine(a/d, d); auto [l2, s2, r2] = refine(r1, b/d); s1.insert(s2.begin(), s2.end()); // set union s1.insert(l2); return {l1, s1, r2}; // l|a, r|b, s|d, l⊥b, r⊥a } set<int> refine(int a[], int n) { if (n == 1) return {a[0]}; if (n == 2) { auto [l,s,r] = refine(a[0], a[1]); s.insert(l); s.insert(r); s.erase(1); return s; } set<int> s; set<int> t = refine(a, n-1); int r0 = a[n-1]; for (auto ti: t) { auto [l, s, r] = refine(ti, r0); s.insert(s); s.insert(l); r0 = r; } s.insert(r0); s.erase(1); return s; }

遞迴加權總和【數學家稱作Ideal】

給定集合，窮舉各種權重組合，得到各種加權總和。

A = {a₁, a₂, a₃}
b = w₁a₁ + w₂a₂ + w₃a₃
c = v₁a₁ + v₂a₂ + v₃a₃ + v₄b
:       :

A = {x³ - 2xy, 2x²y - y² + x, x² + 1}
b = 2y (x³ - 2xy) + x (2x²y - y² + x) = -3xy² - x²
c = y (x³ - 2xy) + xy (x² + 1) + (x - y + 1) (-3xy² - x²)
:       :

數學式子展開之後，其實等同於沒有遞迴的加權總和。

span(A) = w₁ a₁ + w₂ a₂ + ...

遞迴餘數【數學家稱作Modular Reduction】

給定模數集合，窮舉各種模數組合，得到各種餘數。

M = {m₁, m₂, m₃}
a ⤳ b (mod m₁)
b ⤳ c (mod m₃)   —→   a ⤳ r (rmod M)
c ⤳ d (mod m₁)
:   :
q ⤳ r (mod m₂)

不斷消滅首項，度數越來越小，最終無法再模。

項有多種排序方式。固定使用同一種，哪一種都可以。

字典順序：先以字母排序，再以度數排序。（部分變數視做常數）
x²y² + x²y + x² + xy² + xy + x + y² + y + 1
^^^^^^^^^^^^^^^   ^^^^^^^^^^^^   ^^^^^^^^^^
       x²               x             1

度數順序：先以度數排序，再以字母排序。
x²y² + x²y + xy² + x² + xy + y² + x + y + 1
^^^^   ^^^^^^^^^   ^^^^^^^^^^^^   ^^^^^   ^
  4        3             2          1     0

遞迴餘數的性質，宛如一般餘數的性質。

a₁ ⤳ r₁           (rmod M)
a₂ ⤳ r₂           (rmod M)
a₁ + a₂ ⤳ r₁ + r₂ (rmod M)

Gröbner Basis

給定被除數集合，實施遞迴加權總和；找到除數集合，可以遞迴整除每一個加權總和。這樣的除數集合，稱作Gröbner Basis。

策略：公因數、單項式。

aᵢ ⤳ 0 (rmod M)   for all aᵢ in span(A)   —→ M is Gröbner Basis of A

演算法（Buchberger's Algorithm）

https://en.wikipedia.org/wiki/Buchberger's_algorithm

遞迴加權總和，總共無限多個，無法一一檢查是否整除。

等價方式：被除數集合納入除數集合。除數集合之中，兩兩元素的S-polynomial，一一檢查是否整除。證明省略。

         lcm(lm(a),lm(b))     lcm(lm(a),lm(b))
s(a,b) = ———————————————— a - ———————————————— b
               lm(a)                lm(b)

lm(): leading monomial
lcm(): least common multiple

a = x³ - 2xy
b = 2x²y - y² + x
lm(a) = x³
lm(b) = 2x²y
lcm(lm(a),lm(b)) = 2x³y
s(a,b) = (2x³y / x³) a - (2x³y / 2x²y) b = -3xy² - x²

所有被除數納入除數。窮舉兩兩除數，計算S-polynomial，試除。如果除不盡，就將餘數納入除數，重新再來一輪。

時間複雜度為指數時間。

演算法（M4GB）

https://github.com/cr-marcstevens/m4gb

目前最快的演算法。