0702 - Pascal

Triunghiul lui Pascal este un aranjament geometric de numere ce poartă numele celebrului matematician francez Blaise Pascal (19 iunie 1623 – 19 august 1662), deoarece el a fost prima persoană care a descoperit importanţa tuturor modelelor din componenţa acestuia.

Triunghiul începe cu numărul 1. Acest rând este considerat rândul 0 al triunghiului. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra (considerând că toate numerele din afara triunghiului sunt întotdeauna zero). Prin urmare, rândul 1 va fi format din 1 = 0 + 1, 1 = 1 + 0, iar rândul 2 va fi format din 1 = 0 + 1, 2 = 1 + 1, 1 = 1 + 0.

Fie n și p două numere naturale nenule cu proprietățile:

• p este număr prim;
• n+1 este o putere naturală a lui p;

Notăm cu M(p) numărul de multipli de p din primele n+1 rânduri ale triunghiului lui Pascal.

Cerința

Să se scrie un program care citeşte numerele naturale n şi p și determină numărul M(p).

Date de intrare

Fișierul de intrare pascalIN.txt conține pe prima linie numerele naturale n și p separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire pascalOUT.txt va conține pe prima linie numărul M(p) cu semnificația de mai sus. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 2 ≤ n ≤ 109
• 2 ≤ p ≤ 103
• 30% din teste au n ≤ 104
• 50% din teste au n ≤ 106

Exemplul 1:

pascalIN.txt

7 2

pascalOUT.txt

9

Explicație

În primele 8 rânduri ale triunghiului se găsesc 9 multipli de 2: 2,4,6,4,10,10,6,20,6.

Exemplul 2:

pascalIN.txt

2196 13

pascalOUT.txt

1660932

Explicație

În primele 2197 rânduri ale triunghiului se găsesc 1660932 multipli de 13.

Rezolvare

#0702 - Pascal
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def calculate_M_pascal(n, p):
    M_p = 0
    current_power = 1
    
    while current_power <= n + 1:
        M_p += (n + 1) // current_power
        current_power *= p
    
    return M_p

def check_restrictions(n, p):
    if not (2 <= n <= 10**9):
        return False
    if not (2 <= p <= 10**3):
        return False
    if n > 10**4 and p > 2:
        return False
    if n > 10**6 and p > 2:
        return False
    return True

def main():
    # Citirea datelor de intrare
    with open('pascalin.txt', 'r') as file:
        n, p = map(int, file.readline().split())

    # Verificare restricții
    if not check_restrictions(n, p):
        print("false")
        return

    # Verificare dacă p este prim
    if not is_prime(p):
        print("false")
        return

    # Calculul lui M(p)
    result = calculate_M_pascal(n, p)

    # Scrierea rezultatului în fișierul de ieșire
    with open('pascalout.txt', 'w') as file:
        file.write(str(result))

if __name__ == "__main__":
    main()