1011 - p3factoriale

Cerința

Se dau a, b, c și p numere naturale, astfel încât a ≥ b + c și p număr prim. Să se afle dacă numărul  este divizibil cu p, și să se afle exponentul lui p în descompunerea în factori primi a acestui număr.

Date de intrare

Programul citește de la tastatură numerele a, b, c și p, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul e, reprezentând exponentul lui p în descompunerea în factori primi a numărului natural . Dacă numărul nu este divizibil cu p, atunci se va afișa 0.

Restricții și precizări

• 1 ≤ a , b , c ≤ 1.000.000.000
• a ≥ b + c
• 2 ≤ p ≤ 1.000

Exemplu:

Intrare

12 4 5 3

Ieșire

3

Explicație

Știm de la matematică faptul că numărul  este natural, deci putem vorbi despre divizibilitatea lui prin p ( Numărul  reprezintă combinări de  elemente luate câte  ).

De asemenea se știe că exponentul numărului prim p în descompunerea în factori primi a numărului a! este , unde prin  am notat partea întreagă a lui .

În exemplul dat avem , deci exponentul este 3.

Rezolvare

def count_p_in_factorial(n, p):
    exponent = 0
    while n % p == 0:
        n //= p
        exponent += 1
    return exponent

def is_divisible_by_p(a, b, c, p):
    exponent_a = count_p_in_factorial(a, p)
    exponent_b = count_p_in_factorial(b, p)
    exponent_c = count_p_in_factorial(c, p)

    if exponent_a - exponent_b - exponent_c < 0:
        return 0

    exponent = exponent_a - exponent_b - exponent_c
    return exponent

def main():
    a, b, c, p = map(int, input().split())

    if a >= b + c:
        exponent = is_divisible_by_p(a, b, c, p)
        print(exponent)
    else:
        print("0")

if __name__ == "__main__":
    main()