#18094: 解法思路(C++版)


es611543 (afa)

學校 : 基隆市私立二信高級中學
編號 : 93767
來源 : [36.227.102.179]
最後登入時間 :
2024-09-25 22:24:13
c662. Hello Oscar -- it's david | From: [218.161.13.235] | 發表日期 : 2019-06-16 17:52

將每1位置找循環則可以分組,例如測資1
0:2 , 1:3 , 2:5 , 3:4 , 4:1 , 5:6 , 6:0
第0個位置的循環為{0,2,5,6,0} 即 0,2,5,6同一組,這組個數 4個
第1個位置的循環為{1,3,4,1} 即1,3,4同一組,這組個數 3個
找出各組的個數,例如測資1分成2組,個數各為4,3求 LCM(4,3)=12

但1000個位置有可能剛好分成25組以上,個數分別為 2,3,5,7,11,13,....,97,? 剛好有前25個不同質數
則其LCM(2,3,5,7,.....97) =2*3*5*7*...*97 會大於 long long
大數求LCM?

我是將每組的個數 分解成 「質因數乘積式」則LCM只需記錄較大的 次方即可
最後只要寫一個 大數*整數 算出LCM值

 
#37687: Re: 解法思路(C++版)


proglohas@gmail.com (david)

學校 : 不指定學校
編號 : 221623
來源 : [114.42.166.68]
最後登入時間 :
2024-07-04 17:52:44
c662. Hello Oscar -- it's david | From: [122.117.95.179] | 發表日期 : 2023-09-29 12:37

long long 會過。

 

 
ZeroJudge Forum