数学 整数論の問題

アメリカMath Is Cool contest (2013-2014 #38)の問題です。
The country of Kurtlandia has a coin worth 11 cents and a coin worth 13 cents. What is the largest number of cents that CANNOT be made using these Kurtlandish coins?
どのように解けばよいでしょう？

No.3 回答者： Tacosan 回答日時： 2019/02/19 01:11

As 11 and 13 are mutually prime the answer is (11-1)(13-1)-1 = 119.

ってやっちゃダメなんだろ～な～.

No.2 回答者： スチールウール 回答日時： 2019/02/18 14:04

13x +11y =k (k=1…10)の解のうち、y<0を満たす解のペアの中でyが最も大きいものを考えると

k=1: 6,-7
2:1,-1
で、このあとは7,-8, 2,-2 8,-9…とkが2増えるたびにxは+1、yは-1されます
つまり、yの最小値はk=9のときx=10,y=-11

N = 11m + kとすると、mが先程求めた数より多いと13,11の0〜の和で表せます
例えば、
N = 11x7 +1=78= 11x7+13x7-11x7=13x7
N = 11x8 +1=89=13x7+1
です

あとは、整理したときに11の係数が負になるものを選べばいいです（0や正になるものは表せる）
一番最初の計算よりm=10,k=9が最大

N=11x10 +9は
11x10 +13x10-11x11 =13x10 + 11x(-1)
となるため、11の係数が負になりやはり無理です
つまり、119が最大の候補

13x + 11y =119（x>0,y>0）
13*10-11 = 119
両辺を引いて
13(x-10)=11(1-y)
13,11は互いに素なので
x=10+11n
y=1-13n
これは（x>0,y>0）を満たすnは存在しない
よって、119が最大

No.1 回答者： usa3usa 回答日時： 2019/02/18 13:06

ふるいにかける

１３の倍数を消す
１１＋１３の倍数を消す
１１＊２＋１３の倍数を消す
：
１１＊１３＋１３の倍数を消す
消されずに残った数の最大値を答える

上記の行為を計画的に効率よく実行することでしょうか