#20084: __公式
kentsai1688@gmail.com
(Ken Tsai)
學校
:
國立科學工業園區實驗高級中學
編號 : 99014
來源 : [118.163.197.175]
最後登入時間 ：
2020-07-19 18:20:13
a*b-a-b
#30759: Re: 公式
a*b-a-b
您好，請問這個公式怎麼來的？如果沒有這個公式，我應該就寫不出來了…@_@~
#30760: Re: 公式
a*b-a-b
您好，請問這個公式怎麼來的？如果沒有這個公式，我應該就寫不出來了…@_@~
我是從同餘最短路去想的
以範例測資a=3 b=7 (如果a>b就交換，不影響結果)
除以3的餘數為0, 1, 2 以這3個數字做為結點
接著對(u = 0, 1, 2)建一條有向邊到(v = (u+7) % 3)邊的權重為7
0 -> 1 : 7
1 -> 2 : 7
2 -> 0 : 7
可以發現圖剛好會形成一個簡單環
所以最晚抵達的結點需要經過 2 (a-1)條邊, 所需最短時間為14 ((a-1)*b)
這代表在14以前我們無法用(a, b)湊出14同餘3的數字，比14小且同餘3的數字就是14-3=11
因此答案就是 (a-1)*b-a = a*b-b-a
臨末教我的 他好電
#30764: Re: 公式
a*b-a-b
您好，請問這個公式怎麼來的？如果沒有這個公式，我應該就寫不出來了…@_@~
我是從同餘最短路去想的以範例測資a=3 b=7 (如果a>b就交換，不影響結果)
除以3的餘數為0, 1, 2 以這3個數字做為結點
接著對(u = 0, 1, 2)建一條有向邊到(v = (u+7) % 3)邊的權重為7
0 -> 1 : 7
1 -> 2 : 7
2 -> 0 : 7
可以發現圖剛好會形成一個簡單環
所以最晚抵達的結點需要經過 2 (a-1)條邊, 所需最短時間為14 ((a-1)*b)
這代表在14以前我們無法用(a, b)湊出14同餘3的數字，比14小且同餘3的數字就是14-3=11
因此答案就是 (a-1)*b-a = a*b-b-a
臨末教我的 他好電
謝謝您的回答