Sumgcd

Se dă un șir $A$ cu $N$ termeni numere naturale nenule. Pentru fiecare termen $A_{i}$, cu $i\geq 2$, definim $B_{i}=\max\{\gcd(A_{i},A_{1}), \gcd(A_{i},A_{2}),\cdots, \gcd(A_{i},A_{i-1}) \}$ și $S(A)=B_{2}+B_{3}+\cdots +B_{N}$, unde $\gcd(x,y)$ este cel mai mare divizor comun al numerelor $x$ și $y$.

Cerință

1. Să se determine $S(A)$.
2. Să se determine o permutare $P$ a numerelor de la $1$ la $N$ pentru care $S(C)$ este maximă, unde $C$ este șirul al cărui termeni sunt definiți prin $C_{i}=A_{P_{i}}$ pentru orice $i$ de la $1$ la $N$.

Date de intrare

Pe prima linie a fișierului sumgcd.in se află numerele $T$ și $N$, unde $T$ reprezintă numărul cerinței. Pe a doua linie se află $N$ numere naturale nenule reprezentând termenii șirului $A$.

Date de ieșire

În fișierul sumgcd.out se va afișa $S(A)$ pentru $T=1$, iar pentru $T=2$ se vor afișa termenii permutării $P$, separați prin spații. Dacă există mai multe soluții, o puteți afișa pe oricare.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq A_{i}\leq 1 \ 000 \ 000$
• La cerința 2, dacă $S(C)$ nu este maximă, se acordă punctaj parțial egal cu $\left( \frac{S(C)}{S(C')}\right)^{4}\cdot 50\%$ din punctajul testului, unde $C'$ este șirul pentru care S(C') e maximă.

Exemplul 1

sumgcd.in

1 5
12 7 15 21 20

sumgcd.out

16

Explicație

Pentru primul test avem $S(A)= \gcd(12,7)+\gcd(15,12)+\gcd(21,7)+\gcd(20,15)=16$.

Exemplul 2

sumgcd.in

2 5
12 7 15 21 20

sumgcd.out

1 5 3 4 2

Explicație

Pentru al doilea test avem permutarea (1, 5, 3, 4, 2) ce corespunde șirului $C = (12,20,15,21,7)$, iar $S(C)=\gcd(12,20)+\gcd(20,15)+\gcd(12,21)+\gcd(7,21)=19$.