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


es611543 (afa)

學校 : 基隆市私立二信高級中學
編號 : 93767
來源 : [114.24.37.174]
最後登入時間 :
2025-06-28 17:08:20

將每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
來源 : [122.117.95.179]
最後登入時間 :
2024-12-30 11:17:25

long long 會過。