例題：HDOJ 1792 A New Change Problem
題意：給定A和B，A和B互質(zhì)，求最大不能組合數(shù)，和不能組合數(shù)的個數(shù)。

基礎(chǔ)知識：
Gcd(A, B) = 1 → Lcm(A, B) = AB
剩余類，把所有整數(shù)劃分成m個等價類，每個等價類由相互同余的整數(shù)組成

任何數(shù)分成m個剩余類，分別為 mk，mk+1，mk+2，……，mk+(m-1)
分別記為{0(mod m)}，{1(mod m)}……
而n的倍數(shù)肯定分布在這m個剩余類中
因為Gcd(m，n)=1，所以每個剩余類中都有一些數(shù)是n的倍數(shù)，并且是平均分配它的旁證，可見HDOJ 1222 Wolf and Rabbit
設(shè) kmin = min{ k | nk ∈ {i (mod m)} }, i ∈ [0, m)
則 nkmin 是{i (mod m)}中n的最小倍數(shù)。特別的，nm ∈ {0 (mod m)}
nkmin 是個標志，它表明{i (mod m)}中nkmin 后面所有數(shù)，即nkmin + jm必定都能被組合出來
那也說明最大不能組合數(shù)必定小于nkmin
我們開始尋找max{ nkmin }
Lcm(m, n) = mn，所以很明顯(m-1)n是最大的
因為(m-1)n是nkmin 中的最大值，所以在剩下的m-1個剩余類中，必定有比它小并且能被m和n組合，這些數(shù)就是(m-1)n -1，(m-1)n -2，……，(m-1)n -(m-1)
所以最大不能被組合數(shù)就是(m-1)n -m

如果m和n不互素，那{1 (mod m)}不能被m組合，同樣也不能被n和m組合

我們能求出各個剩余類的nkmin之后，不能組合數(shù)的個數(shù)就是每個剩余類中小于各自nkmin的數(shù)的個數(shù)總和。
觀察如下：
M = 5，N = 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……
紅色的就是不能組合數(shù)，可以看出在剩余類中它的數(shù)目有規(guī)律
Total = [0+1+2] + [0+1]
因為m和n互質(zhì)，必有一個不完全周期
整理以后，可得公式 Total = (n-1)*(m-1)/2

轉(zhuǎn)載于:https://www.cnblogs.com/anderson0/archive/2009/05/14/1456964.html

總結(jié)

以上是生活随笔為你收集整理的1792 关于数论中的互质数的最大不能组合数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。