Quotient(Under Construction!)

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))
floor(n/1) + floor(n/2) + ... + floor(n/n)

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(Under Construction!)

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

GCD-free Basis

請見專著《Algorithmic Number Theory》

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

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

Gröbner Basis

遞迴加權總和【數學家稱作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

目前最快的演算法。