1902 - DouaMii17

Cerința

Primele 2017 numere naturale, având fiecare exact 2017 divizori naturali, s-au gândit la început de nou an să-şi pună divizorii împreună, în ordine crescătoare, astfel se vor amesteca şi vor mai socializa şi ei în mod democratic. Marele conducător KWI s-a gândit să bage zâzanie între ei şi a început să le pună n întrebări de genul “-Domnule x, faci cumva parte din societatea secretă a divizorilor celor 2017 numere cu câte 2017 divizori?”. Să sperăm că până în anul 2017 va primi toate răspunsurile şi toată lumea va fi fericită.

Date de intrare

Fișierul de intrare douamii17.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, pentru care trebuie să verificăm dacă se află în şirul divizorilor primelor 2017 numere naturale care au exact 2017 divizori fiecare.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire douamii17.out va conține pe linia i, pentru fiecare i de la 1 la n, 1 dacă al i-lea număr de pe linia a doua a fişierului de intrare se află în şirul divizorilor şi 0 altfel.

În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 500.000.000

Exemple

Exemplul 1

douamii17.in

5

1 2 18 23 9

ecran

Datele sunt introduse corect.

douamii17.out

1

1

0

1

1

Exemplul 2

douamii17.in

5

10 20 30 40 50

ecran

Datele sunt introduse corect.

douamii17.out

0

0

0

0

0

Exemplul 3

douamii17.in

3

-5 1000000000 2000000000

ecran

Datele nu corespund restricțiilor impuse.

douamii17.out

Rezolvare

# 1902 - DouaMii17
import math

def is_valid(num_count, num_list):
    if num_count < 1 or num_count > 1000000:
        return False
    for num in num_list:
        if num < 1 or num >= 500000000:
            return False
    return True

def calculate_divisors():
    prime_flags = [0] * 20001
    prime_list = []
    divisor_flags = [0] * (500000001)
    prime_count = 0
    current_num = 2
    while prime_count < 2017:
        if prime_flags[current_num] == 0:
            prime_count += 1
            prime_list.append(current_num)
            current_square = current_num * current_num
            while current_square < 20000:
                prime_flags[current_square] = 1
                current_square += current_num
        current_num += 1

    divisor_flags[1] = 1
    for i in range(2017):
        current_prime = prime_list[i]
        while current_prime < 500000000:
            divisor_flags[current_prime] = 1
            current_prime *= prime_list[i]

    return divisor_flags

if __name__ == "__main__":
    with open("douamii17.in") as input_file:
        num_count = int(input_file.readline().strip())
        num_list = list(map(int, input_file.readline().strip().split()))
        if not is_valid(num_count, num_list):
            print("The data does not meet the required restrictions.")
            exit(0)

    divisors = calculate_divisors()

    print("The input data is correct.")
    with open("douamii17.out", "w") as output_file:
        for num in num_list:
            output_file.write(str(divisors[num]) + "\n")

Explicatie

is_valid(n, nums): Această funcție primește doi parametri, n și nums. Verifică dacă numărul de elemente din lista nums este cel puțin 1 și cel mult 1.000.000 și dacă fiecare element din listă este mai mare decât 0 și mai mic decât 500.000.000. În cazul în care aceste condiții sunt îndeplinite, funcția returnează True, în caz contrar returnează False.

calculate_divisors(): Această funcție calculează șirul de divizori pentru primele 2017 numere naturale care au exact 2017 divizori.

Folosește două liste, b și p, pentru a marca numerele prime și numerele prime anterioare din șirul de divizori. După ce lista p este completată cu primele 2017 numere prime, funcția calculează divizorii pentru fiecare număr prim, înmulțindu-l cu el însuși, apoi cu fiecare număr prim anterioară din șir, până când ajunge la 500.000.000.

Rezultatul este returnat sub formă de listă, unde fiecare element are valoarea 1 dacă se află în șirul de divizori, sau 0 altfel.

main(): Această funcție este punctul de intrare în program.

Verifică dacă datele de intrare sunt valide, apoi apelează funcția calculate_divisors() pentru a obține șirul de divizori. Rezultatul este scris în fișierul douamii17.out și afișat pe ecran.