[問題] ACM 10090(已解決)
題目：
http://luckycat.kshs.kh.edu.tw/homework/q10090.htm
我的程式碼：http://ideone.com/eoz4c
這題我是用Extended Euclid's Algorithm來做的
以下是我的想法
============================================================================
n1*x + n2*y = gcd(n1,n2) = d ..... 根據Extended Euclid's Algorithm得來的
n1*m1 + n2*m2 = n ................ 從題目中列出來的
結合上面兩個式子可以得到m1和m2的 general solution，其中 t 是整數
m1 = n*x/d + n2*t/d .........(3)
m2 = n*y/d - n1*t/d .........(4)
由於m1、m2、n1、n2都是 >=0，由此可以推出t的範圍
ceil( -x*n/n2 ) <= t <= floor( y*n/n1 ) (如果 t 的範圍是個空集合，則此題無解)
題目要求找最小的V，c1*m1 + c2*m2 = V
把(3)和(4)帶進去可以得到底下的式子
c1*(n*x/d + n2*t/d) + c2*(n*y/d - n1*t/d) = V
整理後
(c1*n2/d - c2*n1/d)*t + (c1*x + c2*y)*n/d = V
所以只要 c1*n2/d - c2*n1/d > 0，t 要選擇最小值 ceil( -x*n/n2 )
反之則要選擇最大值 floor( y*n/n1 )
最後把 t 帶回(3)和(4)則可得到題目所要的m1和m2
============================================================================
可是當我測試到下面兩組測資時卻發現m1或m2有一個是負數
133356304
1870 8365
2572 3204
1791
1 21
10 13
0
上面列的公式都已經確定讓m1和m2大於等於零，怎麼還會跑出負數的結果?
請問是不是式子哪裡考慮的不夠周詳?
數學能力不夠好...想了一整天還想不出原因...
麻煩前輩們幫忙一下
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.111.129.79
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
