3295 - Perm Euler: Difference between revisions
Pagină nouă: == 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, '''... |
|||
| Line 20: | Line 20: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
def phi(n): | def phi(n): | ||
result = n | result = n | ||
| Line 41: | Line 35: | ||
return result | return result | ||
def is_permutation(a, b): | def is_permutation(a, b): | ||
| Line 46: | Line 41: | ||
dict_b = {c: str(b).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 | return dict_a == dict_b | ||
if __name__ == '__main__': | if __name__ == '__main__': | ||
with open('permeuler.in', 'r') as f: | with open('permeuler.in', 'r') as f: | ||
nums = list(map(int, f.readline().split())) | nums = list(map(int, f.readline().split())) | ||
| Line 66: | Line 60: | ||
with open('permeuler.out', 'w') as f: | with open('permeuler.out', 'w') as f: | ||
f.write(str(result)) | f.write(str(result)) | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Revision as of 19:29, 18 March 2023
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
Fișierul de ieșire permeuler.out va conține pe prima linie primul număr x pentru care φ(x) e o permutare a lui x și fracția x/φ(x) are valoare minimă.
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 introduse corespund restricțiilor impuse.
- 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> def phi(n):
result = n
i = 2
while i*i <= n:
if n % i == 0:
while n % i == 0:
n //= i
result -= result // i
i += 1
if n > 1:
result -= result // n
return result
def is_permutation(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:
nums = list(map(int, f.readline().split()))
min_ratio = float('inf')
result = 0
for n in nums:
phin = phi(n)
ratio = n / phin
if is_permutation(n, phin) and ratio < min_ratio:
min_ratio = ratio
result = n
with open('permeuler.out', 'w') as f:
f.write(str(result))
</syntaxhighlight>