---

在整個上行過程中是否可以有後退？

舉例解釋我的提法，假設一個梯子10級，每次向上爬7級，或者向下4級

上行：第0級－第7級－（退下）－第3級－第10級

下行：第10－第6－第2－（向上）－第9－第5－第1－up－第8－第4－第0

這樣的方式是否可以？

 

 

---

btw，第7測資很讓人Orz。

123 456 如何解出192？～請示範走走看？

 

---

看討論.. 

不用管題意

出題的表達敘述真的很糟糕
「(2數+起來)/最大公因數 -1」

 

---

我想請教我的想法哪裡錯了?

        Xa-Yb=0

我想整個過程總共要上升X次，要下降Y次

最後回到地面所以等於零

因此求a,b得最小公倍數就是梯子的高度n

不過這樣會得到WA

用(a+b)/gcd(a,b)-1就過了

想知道為什麼解法是這樣及解法的思路.

感謝看完 ^^

 

 

---

想法大約是這樣，但是每上幾次 a 階，上到超過 b 時，就要下降 b ，否則答案會太大。

 

---

  樓樓上別鬧了，解題不管題意要管甚麼呢?

  題意大約可以解讀為：a 與 b 可重疊的最小值 ( gcd( a, b ) ) => a 與 b 重疊長度最大值

  =>  假設 g = gcd( a, b )

        在 g != a 或 g != b 的情況下 ( g = a => 答: a , g = b => 答: b )

a , b 不重疊的長度為 a + b

=>  正解：a + b - g

 

 

---

更正：g = a => b , g = b => a  

---

反正就是藉由爬上爬下 爬到頂點 ，最後會再回到地面上。 來求出最小值

一直爬上，只會讓階層變得更大  --- 公理1
一直爬下，可能會到地面 ----公理2

接著 爬上去a階層 之後，接下來要爬下去  b 層 ，還是繼續爬上 a 層 ？請自行思考ㄅXD

 

---

int f(int a,int b)
{
 int n, m;
 for ( n=m=a; m; m+=a) // up a
 {
  if (m>n)
   n = m;
  if (!(m%=b)) // down b until m>=0
   break;
 }
 return n;
}

Clearly, f(a,b)=f(b,a).

If a and b are relatively prime then
 f(a,b) = a
        + max{(i*a) mod b}, 0≦i＜b (form a complete residue system modulo b, i.e {0,1,…b-1})

Therefore, you can get the formula f(a,b) for arbitrary nature number a and b.