#20084: 公式


kentsai1688@gmail.com (Ken Tsai)

School : 國立科學工業園區實驗高級中學
ID : 99014
IP address : [118.163.197.175]
Last Login :
2020-07-19 18:20:13
e320. NOIP2017 Day1.1.小凯的疑惑 -- NOIP2017提高组Day1第一题 | From: [180.177.106.98] | Post Date : 2019-11-26 20:16

a*b-a-b

 
#30759: Re: 公式


relyl (rely)

School : No School
ID : 113748
IP address : [36.237.97.176]
Last Login :
2022-06-27 19:22:04
e320. NOIP2017 Day1.1.小凯的疑惑 -- NOIP2017提高组Day1第一题 | From: [36.237.192.247] | Post Date : 2022-06-10 22:21

a*b-a-b


您好,請問這個公式怎麼來的?如果沒有這個公式,我應該就寫不出來了…@_@~

 
#30760: Re: 公式


fire5386 (becaidorz)

School : 國立清華大學
ID : 115822
IP address : [101.12.147.118]
Last Login :
2024-05-19 09:33:31
e320. NOIP2017 Day1.1.小凯的疑惑 -- NOIP2017提高组Day1第一题 | From: [114.25.84.225] | Post Date : 2022-06-11 00:01

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: 公式


relyl (rely)

School : No School
ID : 113748
IP address : [36.237.97.176]
Last Login :
2022-06-27 19:22:04
e320. NOIP2017 Day1.1.小凯的疑惑 -- NOIP2017提高组Day1第一题 | From: [36.237.192.247] | Post Date : 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