LCM ճանապարհներ
Էմիլենդում կան
N քաղաքներ՝ համարակալված 1-ից N թվերով։ Էմիլը գտնվում է առաջին քաղաքում և ցանկանում է հասնել N-րդ քաղաք։ Ամեն քաղաքի կցված է թիվ (i-րդ քաղաքին կցված է A[i] թիվը)։ Կամայական i < j համարներով քաղաքների միջև կա ուղղորդված ճանապարհ i-ից j, որի երկարությունը հավասար է LCM(A[i], A[j]) / A[i]։ Էմիլը ցանկանում է պարզել 1-ին քաղաքից N-րդ քաղաք տանող գումարային երկարությամբ կարճագույն ճանապարհի երկարությունը:Մուտքային տվյալներ
Առաջին և երկրորդ տողերում տրված են համապատասխանաբար
T և N թվերը:Եթե
T=0, ապա հաջորդ տողում տրված են լինելու N բնական թվեր՝ A[1], A[2], ... A[N]։Եթե
T=1, ապա հաջորդ տողում թվեր տրված չեն լինելու, և համարելու ենք, որ i-րդ քաղաքին կցված է i թիվը (A[1]=1, A[2]=2, ... A[N]=N)։Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝
1-ից N տանող կարճագույն ճանապարհի երկարությունը։Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (6 միավոր)
T=0, N ≤ 20,1≤ A[i] ≤ 100.000
- Ենթախնդիր 2 (11 միավոր)
T=0, N ≤ 1000,1≤ A[i] ≤ 100.000
- Ենթախնդիր 3 (23 միավոր)
T=0, N ≤ 100.000 և բոլոր A[i]-երը 2-ի աստիճաններ են,1≤ A[i] ≤ 100.000
- Ենթախնդիր 4 (31 միավոր)
T=0, N ≤ 100.000,1≤ A[i] ≤ 100.000
- Ենթախնդիր 5 (10 միավոր)
T=1, N ≤ 100.000
- Ենթախնդիր 6 (19 միավոր)
T=1, N ≤ 1012
Օրինակ
Մուտք | Ելք |
0
8
28 35 30 26 20 34 34 33 | 22 |
0
7
21 15 20 13 21 15 22 | 20 |
1
42 | 12 |
Բացատրություն
Առաջին օրինակում 1-ին քաղաքից կարելի է գնալ 2-րդ քաղաք՝ անցնելով 5 երկարության ճանապարհով։ 2-րդ քաղաքից կարելի է գնալ 3-րդ քաղաք՝ անցնելով 6 երկարության ճանապարհով։ 3-րդ քաղաքից կարելի է գնալ 8-րդ քաղաք՝ անցնելով 11 երկարության ճանապարհով։
Երրորդ օրինակում 1-ին քաղաքից կարելի է գնալ 7-րդ քաղաք՝ անցնելով 7 երկարության ճանապարհով։ 7-րդ քաղաքից կարելի է գնալ 14-րդ քաղաք՝ անցնելով 2 երկարության ճանապարհով։ 14-րդ քաղաքից կարելի է գնալ 42-րդ քաղաք՝ անցնելով 3 երկարության ճանապարհով։
Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 1.5 seconds
Memory limit: 512 MB
Output limit: 1 MB