2597 - PermutarePow

Cerința

Fie ∆ o permutare de gradul n. Se cere să se calculeze perioada principală a funcției f(x) = ∆^x.

Date de intrare

Fișierul de intrare permutarepowin.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte separate prin spații, reprezentând valorile permutării ∆.

Date de ieșire

Fișierul de ieșire permutarepowout.txt va conține pe prima linie numărul P, reprezentând perioada principală a funcției f.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• Numerele de pe a doua linie vor aparține intervalului [1,n]
• Despre permutări

Exemplul 1

permutarepowin.txt

4

3 4 2 1

permutarepowout.txt

Datele introduse corespund restricțiilor impuse.

4

Explicație

Se observă că ∆ = ∆^5, deci perioada principală este 4.

Exemplul 2

permutarepowin.txt

5

1 2 3 4 6

permutarepowout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 2597 - PermutarePow
import math


def validare(permutare_intrare):           # functia de validare a datelor de intrare
    n_intrare = len(permutare_intrare)
    if n_intrare < 1 or n_intrare > 1000000:
        raise ValueError

    for numar in permutare_intrare:
        if numar < 1 or numar > n_intrare:    # fiecare numar trebuie sa fie intre 1 si n
            raise ValueError

    fisier_iesire.write("Datele introduse corespund restrictiilor impuse.\n")


def perioada_principala(permutare_intrare):
    n_intrare = len(permutare_intrare)
    vizitat = [False] * n_intrare
    cicluri = []

    for i in range(n_intrare):
        if not vizitat[i]:
            ciclu = 0
            j = i
            while not vizitat[j]:
                vizitat[j] = True
                ciclu += 1
                j = permutare_intrare[j] - 1
            cicluri.append(ciclu)

    p_curent_local = cicluri[0]
    for i in range(1, len(cicluri)):
        p_curent_local = (p_curent_local * cicluri[i]) // math.gcd(p_curent_local, cicluri[i])

    return p_curent_local


if __name__ == '__main__':
    fisier_intrare = open("permutarepowin.txt", "r")
    fisier_iesire = open("permutarepowout.txt", "w")

    try:
        n = int(fisier_intrare.readline())
        permutare = list(map(int, fisier_intrare.readline().split()))

        validare(permutare)                 # apelul functiei de validare
        p_curent = perioada_principala(permutare)  # apelul functiei de rezolvare

        fisier_iesire.write(str(p_curent))

    except ValueError:
        fisier_iesire.write("Datele introduse nu corespund restrictiilor impuse.")