如何解決 NOIP 2017 day1 t1？

就是兩種不同硬幣a，b，互素，數量不限，請問他們不能組合出的最大面額是多少，比如3，7不能組合出的面額中11最大，我當時猜的答案是

a*b-（a+b）請問對嘛？我用暴力舉的例子都行，在線等急

若x無法用a和b組合出來，則存在整數p和q，使得

x=ap+bq = a(p-b)+b(q+a)且p&>0, q&<0, p-b&<0,q+a&>0

於是0&

最大的x在p=b-1, q=-1時取得，即x*=a(b-1)+b(-1) = ab - a - b

對於任意正整數N，N = ap + bq的通解可以寫為p = p0 + bk, q = q0 - ak，p0和q0是任意一組解，不過這裡不重要。一個單調遞增，一個單調遞減，那要求其中沒有p和q都非負的解，又因為N是正整數所以顯然p和q不會同時為負，那就要求p從負變為非負的同時，q從非負變為負了，不妨設p0就是剛好為負的那組，p0+b就是非負的，那麼：-b &<= p0 &< 0，0 &<=q0 &< a，代回到N = ap0 + bq0里，p0和q0都取最大可能的值，就有max(N) = a(-1) + b(a-1) = ab - a - b

首先不會做不要方 看看暴力怎麼打 於是有了個f[i]表示i是否能表示出來的線性dp(演算法競賽基本套路之打暴力)

然後注意到題目的特性 不是三個數也不是n個數就是兩個數 可以考慮分開考慮 ， 或直接注意到若f[i]為真則f[i+b]為真(演算法競賽基本套路之發現問題的特殊性)

於是考慮g[i]表示到達模b余i的數最少需要幾個a(演算法競賽基本套路之優化狀態) 於是有了個狀態比較少的線性做法 g[i]=g[(i-a)modb]+1

最後發現他們兩個互質 a*0,1,...b-1 遍布整個模b剩餘系 故最大的g為g[a*(b-1) mod b] 故答案為a*(b-1)-b (演算法競賽基本套路之小學數學)

或者直接猜答案(演算法競賽基本套路之打表找規律)

這裡是一個掛了40分的ZZ。

不妨假設

不妨考慮對於每一個0到b-1之間的x，最小的滿足 的k。顯然 是最大的模b等於x的不能被表示出的數。

然後因為a、b互質，所以最大的k對應的最大的x一定是b-a。所以可以用逆元求出此時的 。 就是答案。

然後發現 化一下就是 。

然而我考場上真的寫了逆元+求phi而且覺得自己非常機智。

這題我碰巧在五個月前見到過，然後群里大牛是這麼證的，我給你默寫一遍...

有個typo，倒數第四行那塊應該是"highest order term"，不是"higher"。

首先對於任意整數k，由a、b互素可知一定存在整數（可取負數）m、n使得k=am+bn

對任意兩組使得上式成立的(m1，n1)，(m2，n2)，有a(m1-m2)=b(n2–-1),由a、b互素知b整除m1–m2,記m1–m2=bt,則符合要求的所有整數對(m，n)=(m1-bt,n1+at) t取任意整數

題目中的k無法用am+bn表示，指的是不存在非負的m、n使得k=am+bn，故當取得的t使得m落在[0,b-1]這個區間時，要有n&<0，故k最大時有m=b-1，n=-1，求得k=ab-a-b