View source for 3295 - Perm Euler

== Cerinţa ==
Indicatorul lui Euler, '''φ(n)''' – câteodată numit funcția phi, e folosit pentru a determina câte numere pozitive mai mici decât '''n''' care sunt relativ prime cu '''n''' există. De exemplu, cum '''1''', '''2''','''4''', '''5''', '''7''' și '''8''' sunt toate mai mici decât '''9''' și sunt relativ prime la '''9''', '''φ(9)=6'''. Numărul '''1''' e considerat a fi relativ prim cu toate numerele naturale, deci '''φ(1)=1'''. În mod interesant, '''φ(87109)=79180''', și se poate observa că '''87109''' e o permutare a lui '''79180'''.

Se consideră un șir de cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000'''. Să se scrie un program care găsește valoarea lui '''n''', pentru care '''φ(n)''' e o permutare a lui n și fracția '''n/φ(n)''' are valoare minimă. Dacă sunt mai multe valori cu aceeași proprietate atunci se scrie prima valoare din șir. Dacă nu sunt valori cu proprietatea menționată se va scrie valoarea '''0'''.
== Date de intrare ==
Fișierul de intrare '''permeuler.in''' conține pe prima linie cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000''', separate prin spații.
== Date de ieşire ==
Dacă datele sunt introduse corect, în fișier se va afișa:'''"Datele sunt introduse corect."''', apoi pe un rând nou fișierul de ieșire '''permeuler.out''' va conține primul număr '''x''' pentru care '''φ(x)''' e o permutare a lui '''x''' și fracția '''x/φ(x)''' are valoare minimă. În cazul în care datele nu respectă restricțiile, se va afișa în fișier:'''"Datele nu corespund restricțiilor impuse."'''.
== Restricții și precizări ==
* în fișier sunt cel mult 10000 de numere
* numerele de pe prima linie a fișierului de intrare vor fi mai mici decât 10.000.000
== Exemplu ==
; permeuler.in
: 1000 345 21 34567 5678 63 345678 1234
; permeuler.out
:Datele sunt introduse corect.
: 21
== Explicație == 
În fișierul de intrare sunt '''2''' numere care îndeplinesc proprietatea cerută de problemă: '''21''' care are '''φ(21)=12''' și raportul '''21/φ(21)=1.75''' și '''63''' care are  '''φ(63)=36'''  și raportul  '''63/φ(63)=1.75'''. În fișierul de ieșire va fi scrisă valoarea '''21'''.
== Rezolvare ==
<syntaxhighlight lang="python" line>
#Funția de verificare a datelor de intrare 
def validare_date(numere):
    if len(numere) > 10000:
        return False
    if not all(0 < n < 10000000 for n in numere):
        return False
    if len(set(numere)) != len(numere):
        return False
    return True
#Funcția calculează indicatorul lui Euler pentru n
def phi(n):
    rezultat = n
    i = 2

    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            rezultat -= rezultat // i
        i += 1

    if n > 1:
        rezultat -= rezultat // n

    return rezultat

#Funcția verifică dacă numerele a este o permutare a lui b și invers
def este_permutare(a, b):
    dict_a = {c: str(a).count(str(c)) for c in range(10)}
    dict_b = {c: str(b).count(str(c)) for c in range(10)}
    return dict_a == dict_b


if __name__ == '__main__':
    with open('permeuler.in', 'r') as f:
        numere = list(map(int, f.readline().split()))

        # Verificăm dacă datele de intrare sunt valide
        if not validare_date(numere):
            f.write("Datele introduse nu  corespund restrictiilor impuse.")
            exit(1)

    minimul_raportului = float('inf')
    rezultat = 0
    # Parcurgem fiecare număr din lista și calculăm indicatorul Euler pentru acesta
    for n in numere:
        phin = phi(n)
        raport = n / phin
        # Verifică dacă n și indicator_n sunt permutări una a celeilalte și dacă raportul este minim
        if este_permutare(n, phin) and raport < minimul_raportului:
            minimul_raportului = raport
            rezultat = n
    #Deschidem fișierul și afișăm mesajul de confirmare si rezultatul
    with open('permeuler.out', 'w') as f:
        f.write("Datele sunt introduse corect.\n")
        f.write(str(rezultat))


</syntaxhighlight>