[理工] [離散]-97中山資工

[GraffitiK (GraffitiK)]

http://www.lib.nsysu.edu.tw/exam/master/eng/infoe/infoe_97.pdf

想請問97中山資工離散
第1題：
寫成等式33x+29y=2490，利用Euclidean algorithm求整數x,y
我最後寫成一般式2490=29[2490(8-33k)]+33[2490(-7+29k)]
                    =29(19920-82170k)+33(-17430+72210k), 對所有k屬於Z
x=-17430+72210k, y=19920-82170k
到這裡就卡住了... 不知道怎麼取k使x,y>=0...

解答是寫成2490=33(-7x2490)+29x(8x2490)
              =33(-17430+29k)[phone]k), 對所有k屬於Z
x=-17430+29k, y=19920-33k
當k=602 or 603時x,y>=0

是我的算式寫錯了嗎？


第5題(b)：
答案為小於等於n的所有完全平方數

當locker被改變偶數次state時會保持open，可是為什麼編號為完全平方數的locker
可以確定被改變偶數次？這裡我兜不起來...哪位可以說明一下嗎...？


謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.121.163.36
→ monkeykej:因為因數個數是奇數
推 monkeykej:改變奇數次才是open，題目說第一個學生是open
→ keepoo:原來他是說 第二個開所有2的倍數 第3人開3的倍數？
→ monkeykej:對
→ keepoo:英文果然是我最大罩門 囧 感謝
→ monkeykej:第1題我看不懂你的意思，既然知道了其中一解，那通解只
→ monkeykej:要x的部分+29k，y的部份-33k就好不是? 你的通解好大隻耶
→ GraffitiK:喔 對, 是改變奇數次才open, 我寫錯了. 第1題是因為
→ GraffitiK:1=29(8-33k)+33(-7+29k), 兩邊乘2490後就變成我寫的那樣
→ GraffitiK:這樣有錯嗎? 可是像小黃離散p.1-51例33也是類似的算法不
→ GraffitiK:是嗎...?