212
技術社區[雲棲]
數論中的定理
定理一：
素數定理：
定理二：設a>1，m,n>0，則
HDU2685就用到上述定理。
定理三：設a>b,(a,b)=1,則
定理四：設
，那麼G的值為：
n為素數:本身
n有多個素因子:1
n隻有一個素因子:該因子
應用題目：HDU2582.
定理五：
，其中
為斐波那契數列。
定理六：給定A和B，A和B互質，最大不能組合數為A*B-A-B，不能組合數的個數為
。
證明：
Gcd(A, B) = 1，Lcm(A, B) = AB
把所有整數劃分成A個等價類，每個等價類由相互同餘的整數組成任何數分成A個剩餘類，分別為 ：
Ak，Ak+1，Ak+2，……，Ak+(A-1)，分別記為{0(mod A)}，{1(mod A)}……
而B的倍數肯定分布在這A個剩餘類中，因為Gcd(A，B)=1，所以每個剩餘類中都有一些數是B的倍數，並且是平均分配它的
旁證，可見HDOJ 1222 Wolf and Rabbit
設 kmin = min{k|Bk∈{i(mod A)}},i ∈ [0, A)
則 Bkmin 是{i (mod A)}中B的最小倍數。特別的，AB ∈ {0 (mod A)}
Bkmin 是個標誌，它表明{i(mod A)}中Bkmin 後麵所有數，即Bkmin + jA必定都能被組合出來
那也說明最大不能組合數必定小於Bkmin
我們開始尋找max{ Bkmin },Lcm(A, B) = AB，所以很明顯(A-1)B是最大的
因為(A-1)B是Bkmin 中的最大值，所以在剩下的A-1個剩餘類中，必定有比它小並且能被A和B組合，這些數就是:
(A-1)B-1，(A-1)B -2，……，(A-1)B -(A-1),所以最大不能被組合數就是(A-1)B -A=AB-A-B
如果A和B不互素，那{1 (mod A)}不能被A組合，同樣也不能被B和A組合
我們能求出各個剩餘類的Bkmin之後，不能組合數的個數就是每個剩餘類中小於各自Bkmin的數的個數總和。
觀察如下：A = 5，B = 3
{0(mod 5)}：0，5，10，15……
{1(mod 5)}：1，6，11，16……
{2(mod 5)}：2，7，12，17……
{3(mod 5)}：3，8，13，18……
{4(mod 5)}：4，9，14，19……
紅色的就是不能組合數，可以看出在剩餘類中它的數目有規律：S = [0+1+2] + [0+1]
因為A和B互質，必有一個不完全周期。
整理後得到結果為：
定理七：
定理八：設
，則有以下兩個結論成立：
(1)
(2)
，
典型題目：SPOJ11239 Code：NUMTRYE
--來自苟神 acdreamer
最後更新：2017-04-03 16:48:47