#20084: 公式
kentsai1688@gmail.com
(Ken Tsai)
學校
:
國立科學工業園區實驗高級中學
編號 : 99014
來源 : [118.163.197.175]
最後登入時間 ：
2020-07-19 18:20:13
#30759: Re: 公式
#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: 公式
e320. NOIP2017 Day1.1.小凯的疑惑
--
NOIP2017提高组Day1第一题
| From: [36.237.192.247] |
發表日期
:
2022-06-11 09:23
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
臨末教我的 他好電
謝謝您的回答
ZeroJudge Forum