Residue - 演算法筆記

餘數一元一次方程式＝餘數除法。

Residue (Fractions). monic linear congruences x ≡ rᵢ (mod mᵢ) , mᵢ are coprime. 南北朝數學著作 ... Residue 高者抑之，下者舉之；有餘者損之，不足者與之。

《老子》 Residue 整數除法：被除數除以除數得到商數與餘數。

分堆到底為止。

分堆、補堆任意次數的時候，除數變成模數，餘數變成留數。

餘數只有一個，留數有無限多個。

只要隨便求出一個餘數，不斷加減模數，就得到各個留數；各個留數皆平等，任選一個當代表都行，通常是寫最接近零、大於等於零的那一個。

一般使用≡全等符號表示各個留數兩兩之間的平等關係。

intquotient=8/3; //求商數，此運算符號稱作「除」。

intremainder=8%3; //求餘數，此運算符號稱作「模」。

intquotient=-8/3; intremainder=-8%3; //結果是負數，要小心處理。

//除數為負值，規則詭異，小心使用。

intq=8/-3; intr=8%-3; intq=-8/-3; intr=-8%-3; 中英對照 中文習慣把留數也稱作餘數。

以下皆用餘數稱呼留數。

中文習慣把全等改稱作同餘。

以下皆用同餘稱呼全等。

dividend被除數 divisor除數 quotient商數 remainder餘數 modulo模數 residue留數→餘數 congruence全等→同餘 餘數運算 residue是數值。

congruence是運算符號。

計算學家重視數值，因此演算法書籍喜愛討論residue；數學家重視性質，因此數學書籍喜愛討論congruence。

實數運算，等於=不是主角，加減乘除才是主角；餘數運算，同餘≡當然也不是主角，加減乘除才是主角。

因此接下來將要討論residue的加減乘除。

Residue(Sum) modulomod 餘數無限多個，任選一個當代表都行。

大家習慣選擇最接近零、大於等於零的那一個餘數。

/*a(modm),(-∞,+∞)→[0,m)*/ intmod(inta,intm) { a%=m; //模 if(a<0)a+=m; //小心負數！ returna; } /*a(modm),(-∞,+∞)→[0,m)*/ intmod(inta,intm) { a%=m; a+=a>>31&m; //不使用判斷式！ returna; } /*a(modm),[-m,m)→[0,m)*/ intupd(inta,intm) { returna+=a>>31&m; } /*a(modm),(-∞,+∞)→[0,m)*/ intmod(inta,intm) { returnupd(a%=m,m); } addition+ 模數相同時，餘數可相加。

8(mod3)+7(mod3)≡15(mod3) 8(mod3)+7(mod3)+6(mod3)≡21(mod3) 模數相同時，mod符號可以精簡成一個，寫在式子後面。

8+7≡15(mod3) 8+7+6≡21(mod3) 餘數加法實際上是「無限多個」加「無限多個」等於「無限多個」。

這三項當中，任取一個餘數當代表都行，等式皆成立。

然而實際計算時，大可不必想得如此複雜，就是加與模，求得最接近零、大於等於零的那一個餘數。

intn=(8%3+7%3)%3; //隨時模，避免溢位。

intn=(8+7)%3; //先加一加，最後才模。

/*a+b≡x(modm),a,b∈(-∞,+∞)*/ intadd(inta,intb,intm) { intx=(a%m+b%m)%m; //隨時模，避免溢位。

if(x<0)x+=m; //小心負數！ returnx; } intadd(inta,intb,intm) { //不使用判斷式！ return(((a%m+b%m)%m)+m)%m; } intadd(inta,intb,intm) { return(((a+b)%m)+m)%m; //先加一加，最後才模。

} 當輸入已經是標準餘數，則可避開模運算，爭取時間。

/*a+b≡x(modm),a,b∈[0,m)*/ intadd(inta,intb,intm) { //0≤a,b0;b>>=1) { if(b&1)x=add(x,a,m); a=add(a,a,m); } returnx; } exponentiation^ 餘數可以有整數次方，等同於連乘。

8(mod3)^3≡8(mod3)×8(mod3)×8(mod3)≡512(mod3) 次方值可以推廣成餘數，但是次方值的模數不是原本模數。

模數是質數p，次方值的模數正是p-1。

根據「費馬小定理」。

2(mod7)^100≡2(mod7)^100(mod6) 模數與底數互質，次方值的模數是「CarmichaelFunctionλ(m)」其中一個因數。

2(mod9)^100≡2(mod9)^100(modλ(9)) 模數與底數互質，次方值的模數是「CoprimeCountingFunctionφ(m)」其中一個因數。

φ(m)因數種類更多、內含錯誤，但是φ(m)比較容易計算。

2(mod9)^100≡2(mod9)^100(modφ(9)) 模數與底數互質，次方值的模數多半不是m-1其中一個因數。

根據「Lehmer'sTotientProblem」。

模數是普通數字，事情相當複雜，不能直接推廣成餘數，此處不討論。

計算λ(m)和φ(m)曠日廢時。

況且我們也不確定是λ(m)和φ(m)的哪一個因數。

如果預先知道λ(m)或φ(m)，就可以預先將次方值模λ(m)或φ(m)，以加速次方運算。

預先知道φ(9)=6 2(mod9)^100 ≡2(mod9)^100(modφ(9)) ≡2(mod9)^100(mod6) ≡2(mod9)^4(mod6) ≡16(mod9) ≡7(mod9) /*a^b≡x(modm)*/ intpow(inta,intb,intm) { //沿用整數次方的演算法 intx=1; for(;b>0;b>>=1) { if(b&1)x=mul(x,a,m); a=mul(a,a,m); } returnx; } UVa374luoguP1226 Residue(Fraction) reciprocal¹⁄ₓ 求乘數，乘積是1。

☐×7≡1(mod5) 移項即是倒數。

1÷7≡☐(mod5)除法風格 ¹⁄₇≡☐(mod5)分數風格 7⁻¹≡☐(mod5)次方風格 7≡☐(mod5)共軛風格 餘數倒數要嘛無解、要嘛無限多解。

如果只看大於等於零、小於模數的答案數量，餘數倒數可能無解、一解。

☐×7≡1(mod5)—→1÷7≡☐(mod5)☐是3 3×☐≡1(mod4)—→1÷3≡☐(mod4)☐是3 2×☐≡1(mod4)—→1÷2≡☐(mod4)☐不存在 1×☐≡1(mod4)—→1÷1≡☐(mod4)☐是1 0×☐≡1(mod4)—→1÷0≡☐(mod4)☐不存在 實數倒數、餘數倒數，意義不同！實數倒數的本質是「等分」，餘數倒數不具備這種意義。

餘數倒數的本質是乘法式子解未知數。

實數倒數、餘數倒數，算法不同！實數倒數的演算法是「長除法」。

餘數倒數的演算法是「輾轉相除法」。

倒數的定義 a×a≡1(modm) 上式重新整理（上式只取其中一個餘數當代表，現在則是考慮所有餘數。

） a×a+m×k=1 使用擴展版本的輾轉相除法，求得a與m的最大公因數，求得倍率a與k，得到我們想要的「a的倒數」。

a與m的最大公因數必須是一（互質），才擁有倒數。

換句話說。

模數是質數：每一個數都有倒數。

模數不是質數：只有跟模數互質的數才有倒數。

/*a×x≡1(modm)*/ intrec(inta,intm) { intd=m,x=0,y=1; while(a!=0) { intq=d/a,r=d%a; d=a;a=r; intt=x-q*y; x=y;y=t; } if(d!=1)return-1; //沒有倒數 returnupd(x,m); //小心負數！ } /*ax+by=d*/ voidextgcd(inta,intb,int&x,int&y,int&d) { if(!b){x=1;y=0;d=a;return;} gcd(b,a%b,y,x,d); y-=(a/b)*x; } /*a×x≡1(modm)*/ intrec(inta,intm) { intd,x,y; extgcd(a,m,x,y,d); returnd==1?upd(x,m):-1; } luoguP1082 reciprocaltable¹⁄₁...¹⁄ₓ（模數是質數） 模數是質數，每一個數都有倒數！ 此時可以預先建立倒數表，預先計算每一個數的倒數。

利用遞迴公式，時間複雜度O(N)。

p%i=p-floor(p÷i)×i p%i≡-floor(p÷i)×i(modp) rec[i]≡-floor(p÷i)×rec[p%i](modp)移項 intrec[100]; voidreciprocal_table(intp) { rec[1]=1; for(inti=2;i reciprocal¹⁄ₓ（模數是質數） 根據「費馬小定理」，模數是質數p，倒數恰是p-2次方。

不必特地撰寫輾轉相除法。

時間複雜度也差不多。

a^p≡a(modp) a^(p-1)≡1(modp)whena≢0(modp) a^(p-2)≡a(modp)whena≢0(modp) /*a×x≡1(modm),misprime*/ intrec(inta,intm) { returnpow(a,m-2,m); } division÷ 求乘數（被乘數）。

☐×7≡22(mod5) 移項即是除法。

22÷7≡☐(mod5) 餘數除法要嘛無解、要嘛無限多解。

如果只看大於等於零、小於模數的答案數量，餘數除法可能無解、一解、多解。

☐×7≡22(mod5)—→22÷7≡☐(mod5)☐是1 ☐×2≡3(mod4)—→3÷2≡☐(mod4)☐不存在 ☐×4≡5(mod10)—→5÷4≡☐(mod10)☐不存在 ☐×3≡0(mod6)—→0÷3≡☐(mod6)☐是0或2 ☐×3≡3(mod12)—→3÷3≡☐(mod12)☐是1或5或9 究竟如何計算餘數除法呢？數學家發明了倒數！ ☐×7≡22(mod5)求乘數 ☐×7×7≡22×7(mod5)等號兩側同乘以「7的倒數」 ☐≡22×7(mod5)「7」乘以「7的倒數」令它是1，就能消掉。

22÷7≡☐≡22×7(mod5)「除以7」變成「乘以7的倒數」 數學家利用等量乘法原理，建立了倒數的概念。

數學家規定：原數與倒數相乘等於1。

因此「除以原數」變成「乘以倒數」，解決了看似無法整除的情況。

預先求出倒數，便可計算餘數除法！ 7≡3(mod5)模5的時候，7的倒數是3。

因為7×3≡1(mod5)。

22÷7≡22×7≡22×3≡66≡1(mod5) 3÷7≡3×7≡3×3≡9≡4(mod5) 2÷7≡2×7≡2×3≡6≡1(mod5) 1÷7≡1×7≡1×3≡3≡3(mod5) /*a÷b≡x(modm),a⊥m*/ intdiv(inta,intb,intm) { //a÷b≡a×b̅(modm) returnmul(a,rec(b,m),m); } 原數與模數互質，可以求得倒數。

原數與模數不互質，必須不斷約分，直到互質： 一、abm一齊約掉三者公因數d，答案不變。

二、bm一齊約掉兩者公因數d，a卻無法約掉d，無解。

三、模數m/d還原成模數m，答案不變。

四、模數m範圍之內有d個答案，記得補寫其他d-1個餘數。

簡易方式是計算d=gcd(b,m)，一口氣約分到底，直接互質。

a÷b≡☐(modm) a/d÷b/d≡☐(modm/d) /*a÷b≡x(modm)*/ vectordiv(inta,intb,intm) { intd=gcd(b,m); if(a%d!=0)return{}; //無解 a/=d;b/=d;m/=d; //約分 intx=mul(a,rec(b,m),m); //正解 //還原模數，1個餘數變成d個餘數。

vectorv(d); v[0]=x; for(inti=1;i luoguP2613 linearcongruenceax≡b(modm) 餘數一元一次方程式＝餘數除法。

Residue(Fractions) moniclinearcongruencesx≡rᵢ(modmᵢ),mᵢarecoprime 南北朝數學著作《孫子算經》有一道題目：今有物不知其數，三三數之賸二，五五數之賸三，七七數之賸二，問物幾何？ 用現代數學術語來說，這個問題就是餘數系統的一元一次方程組，而且係數皆是一，而且模數兩兩互質。

{x≡2(mod3) {x≡3(mod5) {x≡2(mod7) 正確答案是105數之賸23。

x≡23(mod105) 演算法是「Garner'sAlgorithm」、「Qin'sAlgorithm」。

演算法（窮舉法） 窮舉法：列出「三三數之賸二」的數字，然後是「五五數之賸三」與「七七數之賸二」。

三個列表都出現的數字，就是正確答案。

{x≡2(mod3)⇔x=...,8,5,2,-1,-4,... {x≡3(mod5)⇔x=...,13,8,3,-2,-7,... {x≡2(mod7)⇔x=...,16,9,2,-5,-12,... 試誤法：一一列出各種答案，試著除以三、五、七。

不幸的是，答案有無限多個，試誤法無法找到所有答案。

然而試誤法讓我們發現答案具有規律。

voidsolve() { for(intx=-1000;x<=+1000;++x) if(x%3==2&&x%5==3&&x%2==7) cout<(999+25)×333÷256≡12(mod165) 999+25是4位數，333是3位數，256是3位數，推測正確答案是4位數： 12+165×6=1002 1002+165=1167 1167+165=1332 ...... 一、當數字很大、式子很長時，此技巧就能發揮功效！ 二、模數們最好兩兩互質，方便套用中國餘數定理。

三、此技巧得到的答案一定是整數；也就是說，當正確答案是整數，才能使用此技巧。

比如說，式子之中有除法，導致正確答案是分數，此時就不能使用此技巧。

四、式子之中若有除法，則令模數是質數，餘數除法保證有唯一解。

承第二點，也就是說，模數們最好都是質數。

五、選定的模數們，其乘積足夠大，大於正確答案時，那麼最後求得的餘數，即是正確答案，不必再推測。

例如求「HilbertMatrix」的反矩陣。

HilbertMatrix由單位分數組成，其反矩陣恰好都是整數。

先將問題轉換成餘數系統，選擇多個模數並且各別以高斯消去法求得反矩陣，最後再用中國餘數定理轉換回整數系統。

Residue(Logarithm) multiplicativeorderord() 求指數，乘冪是1。

2^☐≡1(mod9) 移項即是乘性階。

ord₉(2)=☐ 餘數乘性階擁有無限多解。

如果只看大於等於零、小於模數的答案數量，餘數乘性階至少一解0。

數學家只取最小正數──次方值的模數。

0^☐≡1(mod9)—→ord₉(0)=☐☐是0 →未定義 1^☐≡1(mod9)—→ord₉(1)=☐☐是0...8 →只取1 2^☐≡1(mod9)—→ord₉(2)=☐☐是0或6 →只取6 3^☐≡1(mod9)—→ord₉(3)=☐☐是0 →未定義 4^☐≡1(mod9)—→ord₉(4)=☐☐是0或3或6 →只取3 5^☐≡1(mod9)—→ord₉(5)=☐☐是0或6 →只取6 6^☐≡1(mod9)—→ord₉(6)=☐☐是0 →未定義 7^☐≡1(mod9)—→ord₉(7)=☐☐是0或3或6 →只取3 8^☐≡1(mod9)—→ord₉(8)=☐☐是0或2或4或6或8 →只取2 實數乘性階、餘數乘性階，意義不同！實數乘性階是0，缺乏討論意義。

餘數乘性階是次方值的模數。

底數與模數互質，才擁有乘性階。

如同倒數。

換句話說。

模數是質數：每一個數都有乘性階。

模數不是質數：只有跟模數互質的數才有乘性階。

試誤法：窮舉次方值。

O(m)。

/*a^x≡1(modm)*/ intord(inta,intm) { for(intx=1;x /*a^x≡1(modm)*/ intord(inta,intm) { intax=1; for(intx=1;x 試誤法：窮舉次方值。

窮舉λ(m)的因數。

λ(m)計算時間較長，改成窮舉φ(m)的因數。

O(sqrt(m))。

/*φ(n)=n×(1-1/p₁)×(1-1/p₂)×...*/ intphi(intn) { intc=n; for(intp=2;p*p<=n;p++) if(n%p==0) { while(n%p==0)n/=p; c-=c/p; } if(n>1)c-=c/n; returnc; } /*a^x≡1(modm)*/ intord(inta,intm) { if(gcd(a,m)!=1)return-1; //無解 //窮舉φ(m)的因數 intphi_m=phi(m); for(intd=1;d*d<=phi_m;++d) if(phi_m%d==0&&pow(a,d,m)==1) returnd; returnphi_m; } /*a^x≡1(modm)*/ intord(inta,intm) { if(gcd(a,m)!=1)return-1; //無解 intphi_m=phi(m),an=1; for(intd=1;d*d<=phi_m;++d) { an=mul(an,a,m); if(an==1)returnd; } returnphi_m; } 試除法：窮舉φ(m)的因數。

時間複雜度我不會算。

一、解的因數不是解。

改成從大到小窮舉因數。

二、解的倍數也是解（若是φ(m)的因數）。

改成由小到大窮舉倍數，φ(m)除以倍數得到因數。

宛如逐步消滅φ(m)的質因數。

/*p₁^e₁×p₂^e₂×...*/ typedefvector>Factor; /*n=p₁^e₁×p₂^e₂×...*/ Factorfactorize(intn) { Factorfac; for(intp=2;p*p<=n;++p) { inte=0; while(n%p==0) { n/=p; e++; } if(e>0)fac.push_back({p,e}); } if(n>1)fac.push_back({n,1}); returnfac; } /*φ(n)=n×(1-1/p₁)×(1-1/p₂)×...*/ intphi(intn) { Factorfac=factorize(n); for(inti=0;iord(inta,intm) { if(gcd(a,m)!=1)return-1; //無解 // if(gcd(a,m)!=1)return{-1,{}}; intn=phi(m); Factorfac=factorize(n); // intN=0; //factorize(order)size //窮舉φ(m)的因數 for(inti=0;i0)fac[N++]=fac[i]; } returnn; // return{n,fac}; //orderandfactorize(order) } discretelogarithmlog()/indexind() 求指數。

2^☐≡7(mod9) 移項即是對數。

ind₂(7(mod9))≡☐(modord₉(2)) 餘數對數屬於NP問題，但是目前還不確定它究竟是P問題或是NP-complete問題，相當特別。

餘數對數的演算法是「Baby-stepGiant-stepAlgorithm」、「Pohlig–HellmanAlgorithm」。

UVa1022511916luoguP4195 演算法（Baby-stepGiant-stepAlgorithm） 簡單起見，首先討論底數與模數互質的情況。

試誤法。

a⁰到aᵐ⁻¹依序分為⌈m/n⌉個區塊，一個區塊有n個數字。

第一區塊採用窮舉法，其餘區塊採用記憶法。

a^x≡b(modm)已知abm，求x。

另外a⊥m。

一、隨便選一個正整數n。

（通常是sqrt(m)） 二、Baby-step，一步一個數字，總共n步，第一區塊： 　甲、計算a⁰,a¹,...,aⁿ⁻¹， 　　　如果等於b，就找到答案了。

三、Giant-step，一步n個數字，總共(⌈m/n⌉-1)步，其餘區塊： 　甲、一口氣處理aⁿ到a²ⁿ⁻¹： 　　　　aⁿ⁺ⁱ≡b 　　　　aⁿ×aⁱ≡b 　　　　aⁱ≡b×rec(aⁿ) 　　　先前計算的a⁰,a¹,...,aⁿ⁻¹， 　　　如果等於b×rec(aⁿ)，就找到答案了。

　乙、一口氣處理a²ⁿ到a³ⁿ⁻¹， 　　　　a²ⁿ⁺ⁱ≡b 　　　　aⁿ×aⁿ×aⁱ≡b 　　　　aⁱ≡b×rec(aⁿ)×rec(aⁿ) 　　　先前計算的a⁰,a¹,...,aⁿ⁻¹， 　　　如果等於b×rec(aⁿ)×rec(aⁿ)，就找到答案了。

　丙、如法炮製。

採用array儲存a⁰到aⁿ⁻¹，索引儲存，空間複雜度O(m)。

Baby-step時間複雜度O(n)，Gaint-step時間複雜度O(m/n)，總時間複雜度O(n+m/n)。

令n=sqrt(m)讓時間複雜度達到最低，成為O(sqrt(m))。

採用binarysearchtree儲存a⁰到aⁿ⁻¹，空間複雜度降為O(n)，時間複雜度升為O(n+(m/n)⋅log(n))。

採用hashtable儲存a⁰到aⁿ⁻¹，應付模數m很大的情況。

大量計算相同底數與模數的log，不必重算Baby-step，總時間複雜度O(n+N(m/n))。

根據計算次數N來升高n，讓時間複雜度達到最低。

/*a^x≡b(modm),a⊥m*/ intind(inta,intb,intm) { if(b==1)return0; //儲存a⁰...aⁿ⁻¹ vectorx(m,-1); //associativearray // mapx; //red-blacktree // unordered_mapx; //hashtable //baby-step:a⁰...aⁿ⁻¹ intn=sqrt(m); intai=1; for(inti=0;i 改變移項方式，避免計算倒數。

缺點是不支援大量計算。

二、Baby-step，一步一個數字，總共n步，第一區塊： 　甲、處理a⁰到aⁿ⁻¹： 　　　　aⁱ≡b 　　　　aⁿ≡b×aⁿ⁻ⁱ 　　　計算baⁿ,...,ba²,ba¹， 　　　如果等於aⁿ，就找到答案了。

三、Giant-step，一步n個數字，總共⌈m/n⌉步，全部區塊： 　甲、一口氣處理aⁿ到a²ⁿ⁻¹： 　　　　aⁿ⁺ⁱ≡b 　　　　a²ⁿ≡b×aⁿ⁻ⁱ 　　　先前計算的baⁿ,...,ba²,ba¹， 　　　如果等於a²ⁿ，就找到答案了。

　乙、如法炮製。

/*a^x≡b(modm),a⊥m*/ intind(inta,intb,intm) { vectorx(m,-1); intn=sqrt(m); intai=1,aq=1; for(inti=0;i 接著討論底數與模數不互質的情況。

約分。

a的次方提出一項，以便約分。

不斷提項，約分到底。

紀錄總共提出幾項，最後計入答案。

/*a^x≡b(modm)*/ intind(inta,intb,intm) { if(b==1)return0; //約分 intc,d,aq=1; for(c=0;(d=gcd(a,m))!=1;c++) { if(b%d!=0)return-1; b/=d;m/=d; aq=mul(aq,a/d,m); if(b==aq)returnc+1; } //小步大步 vectorx(m,-1); intn=sqrt(m); intai=1; for(inti=0;i 演算法（Pohlig–HellmanAlgorithm） 當次方的模數很大，利用中國餘數定理，將一個大模數改成多個小模數，小模數是質因數次方。

當次方的新模數仍然很大，利用「多項式求係數」演算法原理，將一個大模數改成多個小模數，小模數是質因數的每種次方。

新餘數視作p進位，從最低位數開始計算，一模一除求得每個位數。

時間複雜度O(sum(pₖ+eₖlog(m)))。

pₖ和eₖ來自次方的模數的質因數分解ord(m)=p₁e₁×p₂e₂×...。

當次方的新新模數仍然很大，利用小步大步演算法加速。

/*a^x≡b(modm),a⊥m*/ intind(inta,intb,intm) { intn; //order Factorfac; //factorize(order) tie(n,fac)=ord(a,m); intN=fac.size(); vector>rm(N); //linearcongruences for(intk=0;kx; intwn=1; intw=pow(a,n/p,m); for(inti=0;i Residue(Root) rootofunity√n1 求底數，乘冪是1。

☐^3≡1(mod9) 移項即是單位根。

∛1≡☐(mod9) 試誤法：窮舉所有底數。

/*x^n≡1(modm)*/ vectorroots_of_unity(intn,intm) { vectorv; for(intx=1;x nthroot√n‾ 求底數。

☐^3≡7(mod9) 移項即是開方。

∛7≡☐(mod9) 餘數開方是否有解：次方值約分、費馬小定理。

如果乘冪與模數不互質，那麼我就不知道該怎麼辦了。

/*x^a≡b(modm),b⊥m*/ boolhas_root(inta,intb,intm) { if(b==0)returntrue; intphi_m=phi(m); intd=gcd(a,phi_m); returnpow(b,phi_m/d,m)==1; } 餘數開方屬於NP-complete問題。

餘數開方的演算法是「Adleman–Manders–MillerAlgorithm」、「Williams'Algorithm」。

ICPC4746luoguP5668 squareroot√‾ 求底數，指數是2。

☐^2≡7(mod9) 移項即是平方根。

√7≡☐(mod9) 根據「歐拉準則」、「二次互反律」，餘數平方根是否有解：a½的費馬小定理，+1有解，-1無解。

如果模數不是質數，那麼我就不知道該怎麼辦了。

/*x^2≡a(modm),misprime*/ boolhas_square_root(inta,intm) { if(a==0||m<=2)returntrue; returnpow(a,(p-1)/2,p)==1; } /*⎛a⎞⎧0ifx²≡a≡0(modp) ⎜———⎟=⎨+1ifx²≡a(modp),pisoddprime ⎝p⎠⎩-1ifx²≢a(modp)*/ intlegendre_symbol(inta,intp) { if(a%p==0)return0; returnpow(a,(p-1)/2,p)==1?+1:-1; } 餘數平方根屬於NP-complete問題。

餘數平方根的演算法是「Tonelli–ShanksAlgorithm」、「CipollaAlgorithm」、「Cipolla–LehmerAlgorithm」。

如果模數不是質數，那麼我就不知道該怎麼辦了。

UVa10831luoguP5491U124195 演算法（Tonelli–ShanksAlgorithm） /*x^2≡a(modm),misprime*/ intsqrt(inta,intm) { if(a==0||m==2)returna; intn=(m-1)/2; if(pow(a,n,m)!=1)return-1; if(m%4==3) { intx=pow(a,(m+1)/4,m); return(x*2<=m)?x:(m-x); } intb=1; while(pow(b,n,m)==1)b++; inti=n,j=0; while(i%2==0) { i/=2;j/=2; intx=mul(pow(a,i,m),pow(b,j,m),m); if(x==m-1)j+=n; } i/=2;j/=2; intx=mul(pow(a,i+1,m),pow(b,j,m),m); return(x*2<=m)?x:(m-x); } 演算法（Cipolla'sAlgorithm） structComplex{inta,b;}; Complexmul(Complexa,Complexb,intw,intm) { return(Complex) { (a.a*b.a+a.b*b.b*w)%m, (a.a*b.b+a.b*b.a)%m //calladd(a,b,m)andmul(a,b,m)ifneeded }; } Complexpow(Complexa,intb,intw,intm) { Complexx={1,0}; for(;b>0;b>>=1) { if(b&1)x=mul(x,a,w,m); a=mul(a,a,w,m); } returnx; } /*x^2≡a(modm),misprime*/ intsqrt(inta,intm) { if(a==0||m==2)returna; intn=(m-1)/2; if(pow(a,n,m)!=1)return-1; intr,w; do{ r=rand()%m; w=sub(mul(r,r,m),a,m); }while(pow(w,n,m)==1); Complexx=pow((Complex){r,1},n+1,w,m); return(x.a*2<=m)?x.a:(m-x.a); } 演算法（Cipolla–LehmerAlgorithm） http://library.msri.org/books/Book44/files/02buhler.pdf solvey²≡c(modp) (1)selectrandomnumberbsuchthatD=b²-4cisnon-residue (2)αisarootof(x²-bx+c) thusβ=α^pisalsoaroot thusc=αβ=α^(p+1) (3)returnα^((p+1)/2) https://arxiv.org/abs/1309.2831 solvey²≡c(modp) (1)h:=(b²-4c)^((p-1)/2)(modp) (2)ifh≡0or1(modp)thens:=0 (3)ifh≡-1(modp)thens:=1 (4)q(x):=x^((p+1)/2)mod(x²-bx+c) whereq(x)=c₁x+c₀forintegersc₀,c₁ (5)y:=sc₀ (6)Returnyastheoutput Residue(PrimitiveRoot) primitiveroot【查無數學運算符號】 複數系統的單位根們，藉由乘方與開方，數格子、繞圈圈，可以得到彼此。

餘數系統的單位根們，多半不可以。

因此數學家創造新名詞「原根」： 條件一、底數的可能範圍是「與模數互質的所有數字」，總共φ(m)個。

這些底數擁有倒數，才可以開方。

條件二、次方值模數規定為φ(m)。

等我想一下原因。

條件三、指數的可能範圍是「與次方值模數互質的所有數字」，總共φ(φ(m))個。

以這些指數進行乘方與開方，才可以得到彼此。

滿足上述條件的底數，稱作「原根」。

由於互質的緣故，原根的每個次方，恰是底數的可能範圍的每個數字。

這個性質相當優美，數學家便以此為定義。

一、原根的每個次方，恰好生成所有與模數互質的數字。

二、模數m是2、4、pⁿ、2pⁿ，原根數量是φ(φ(m))個；模數m是其他數字，沒有原根。

p是奇質數，n是正整數。

試誤法：窮舉底數。

針對一種底數，窮舉指數。

試除法：窮舉底數。

針對一種底數，窮舉φ(m)的因數。

質因數分解φ(m)，得到質因數p₁p₂...。

針對一種底數x，窮舉質因數p₁p₂...。

如果x^(φ(m)/p₁)x^(φ(m)/p₂)...皆非1，x就是原根。

（φ(m)改成λ(m)，檢測次數更少；然而λ(m)更難算。

） /*x^φ(m)≡1(modm),xisgenerator*/ boolhas_primitive_root(intm) { if(m<=1)returnfalse; if(m==2&&m==4)returntrue; if(m%2==0)m/=2; if(m%2==0)returnfalse; //https://mathoverflow.net/questions/106313/ returnis_prime_power(m); } boolhas_primitive_root(Factor&fac_m) { intN=fac_m.size(); if(N==0||N>2)returnfalse; int&p1=fac_m[0].first; int&e1=fac_m[0].second; if(N==1&&p1==2&&e1>2)returnfalse; if(N==2&&!(p1==2&&e1==1))returnfalse; returntrue; } boolis_primitive_root(intx,intm) { intphi_m=phi(m); for(inti=1;iprimitive_root(intm) { Factorfac_m=factorize(m); if(!has_primitive_root(fac_m))return{}; intphi_m=phi(m,fac_m); Factorfac_phi_m=factorize(phi_m); intg=least_primitive_root(m,phi_m,fac_phi_m); if(g==-1)return{}; vectorv; for(inti=1,gi=g;i<=phi_m;i++,gi=mul(gi,g,m)) if(gcd(i,phi_m)==1) v.push_back(gi); //g^i sort(v.begin(),v.end()); returnv; } luoguP6091 餘數開方可以利用原根 4^5與8^3誰比較大？ 底數換成一樣，就能比較大小了。

4^5=(2^2)^5=2^10 8^3=(2^3)^3=2^9 x^a≡b(modm)已知abm，求x。

令模m的其中一個原根是g，作為底數。

令x=g^p，b=g^q 原式變成g^ap≡g^q(modm) 繼而變成ap≡q(modφ(m)) 一、g^φ(m)≡1(modm)求g，原根 二、b≡g^q(modm)求q，對數 三、ap≡q(modφ(m))求p，除法 四、x≡g^p(modm)求x，次方 Residue(Group) 餘數系統的特色：有限範圍 餘數系統有個非常重要的特性：數字大於等於零、不超過模數。

電腦只能處理有限範圍的數字。

餘數系統得以發揮功效。

實數系統的加法表、乘法表 +|0123...×|0123... --|-----------------|--------------- 0|0123...0|0000... 1|1234...1|0123... 2|2345...2|0246... 3|3456...3|0369... :|:::::|:::: 餘數系統的加法表、乘法表 (mod1)(mod2)(mod3)(mod4)(mod5) +|0+|01+|012+|0123+|01234 --|----|-------|----------|-------------|-------------- 0|00|010|0120|01230|01234 1|101|1201|12301|12340 2|2012|23012|23401 3|30123|34012 4|40123 (mod1)(mod2)(mod3)(mod4)(mod5) ×|0×|01×|012×|0123×|01234 --|----|-------|----------|-------------|-------------- 0|00|000|0000|00000|00000 1|011|0121|01231|01234 2|0212|02022|02413 3|03213|03142 4|04321 連加循環 餘數系統有個非常重要的特性：數字循環出現、甚至全部出現。

不斷連加，導致循環。

畫在圈圈內部，更清楚。

連加畫在圓的等分點上，得以構造正多邊形、正多角星。

連加畫在數線上，得以連結到最小公倍數的概念。

循環節長度等於「最小公倍數除以連加數」，也等於「模數除以最大公因數」。

請讀者自行按圖推理。

當模數是連加數的倍數（連加數是模數的因數）（連加數整除模數），大多數情況無法遭遇全部數字，除非連加數、模數是一。

考慮所有情況，歸納簡潔結論：連加數與模數，最大公因數不等於一（不互質），遭遇部分數字；最大公因數等於一（互質），遭遇全部數字。

簡單一句話：互質，遭遇全部數字。

順帶一提，「與模數互質的連加數」總共有φ(m)個。

連乘循環 不斷連乘，導致循環。

加法循環，跳躍很規律；一種連加數，只有一種循環節。

乘法循環，跳躍沒規律；一種連乘數，擁有各種循環節。

想要確認循環節起點、循環節長度，可以使用Floyd'sAlgorithm或Brent'sAlgorithm。

乘法群 數學家傾向討論性質優美的事物。

首先區隔「與模數互質的數字」和「不與模數互質的數字」，只取前者。

「與模數互質的數字」不斷相乘，絕不會得到「不與模數互質的數字」，而且所有數字都位於某個循環節之內。

由於與模數互質，每個數字都只有唯一一個倒數，餘數除法亦成立！乘法正向跳躍，除法反向跳躍，雙向都通。

「與模數互質的數字」暨乘法除法，性質優美，自成一格，數學家稱作「乘法群」。

一種模數得到一種乘法群。

順帶一提，「與模數互質的數字」總共有φ(m)個。

次方循環 連乘循環的特例。

起點是零次方。

循環長度必定是λ(m)的因數、或者是φ(m)的某些因數。

求得確切因數，目前沒有快速演算法，只能使用試誤法。

原根 首先取出「與模數互質的數字」當作底數。

引入乘法群的觀點，這些底數的任意次方，仍是「與模數互質的數字」。

從中取出「遭遇所有與模數互質的數字」的底數。

模數是2、4、pⁿ、2pⁿ才有可能。

p是大於2的質數，n是正整數。

求得原根，目前沒有快速演算法，只能使用試誤法。

但是只要求得其中一個原根，就容易求得所有原根。

手法是連加循環！ 每種次方剛好遭遇每種數字。

依照遭遇順序，重新串成一圈。

以原根的某個次方（某個次方連加數），嘗試當作新的原根。

只有「與次方值模數互質的次方數」才是合適的次方數。

再來一個例子。

模數13，互質數字12...12，總共φ(13)=12個。

試誤法求得其中一個原根2，上述互質數字依照原根2的次方順序重新串成一圈，2⁰...2¹¹。

次方模數φ(13)=12，互質數字15711，總共φ(φ(13))=4個，當作次方連加數。

次方連加數1，得到原根2¹。

次方連加數5，得到原根2⁵。

次方連加數7，得到原根2⁷。

次方連加數11，得到原根2¹¹。

2¹2⁵2⁷2¹¹分別等於26117。

得到模數13的所有原根。

Residue(Polynomial) polynomial∑n-1i=0cᵢxⁱ 模數相同時，餘數們可以構成餘數多項式。

x³+2x²-5x+1(mod3) 係數通常是寫最接近零、大於等於零的那一個。

x³+2x²-5x+1≡x³+2x²+x+1(mod3) factorizationn=∏ω(n)k=1pₖeₖ 整數：列舉質數、判斷質數、質因數分解、最大公因數。

列舉質數：2,3,5,7,11,... 判斷質數：97isaprimenumber 質因數分解：999=3×3x3x37 最大公因數：gcd(104,112,116)=4 餘數：不存在質數的概念。

即便是餘數1也可以乘法分解。

列舉質數：2(mod8),3(mod8),...✘ 判斷質數：97(mod8)isaprimenumber✘ 質因數分解：999≡3×3x3x37(mod8)✘ 最大公因數：gcd(104,112,116)≡4(mod8)✘ polynomialfactorizationf(x)=∏deg(f)i=0(x-aᵢ) 整數多項式：列舉質式、判斷質式、因式分解、最大公因式。

列舉質式：x,x+1,x+2,... 判斷質式：x²+x+1isanirreduciblepolynomial 因式分解：2x²+5x+2=(2x+1)(x+2) 最大公因式：gcd(x²-4x+4,x²-x-2)=x-2 餘數多項式：存在質式的概念。

乘法分解受到次方的限制。

列舉質式：x(mod2),x+1(mod2),x²+x+1(mod2),... 判斷質式：x³+x+1(mod2)isanirreduciblepolynomial 因式分解：x²+1(mod2)≡x+1(mod2)×x+1(mod2) 最大公因式：gcd(x³+1(mod2),x²+1(mod2))≡x+1(mod2) polynomialcongruencef(x)≡b(modm) 模數相同時，餘數們可以構成餘數方程式（等式）：左右兩式同餘（相等）。

x²-2x+1≡3x²+x+1(mod5) 餘數方程式求解，化作餘數方程式求根。

x³+2x²-5x+1≡0(mod3) 簡單的演算法是試誤法：窮舉答案，代入計算。

x≡1(mod3) 當模數是質數，根據「PolynomialRemainderTheorem」與「Lagrange'sTheorem」，N-1次餘數多項式方程式頂多N種解。

當模數是質數，大家習慣視作FiniteField的特例。

演算法是有限體多項式分解「Cantor–ZassenhausAlgorithm」的簡化。

【尚待確認】 Cantor–Zassenhaus(f) { f=gcd(f,x^p-x) if(deg(f)==1)returnroot(f) while(true) { b=random() g=gcd(f,(x+b)^((p-1)/2)-1) if(0