Vizualizare sursă pentru „1011 - p3factoriale”


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

= Date de intrare =
Programul citește de la tastatură numerele <code>a</code>, <code>b</code>, <code>c</code> și <code>p</code>, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>e</code>, reprezentând exponentul lui <code>p</code> în descompunerea în factori primi a numărului natural . Dacă numărul nu este divizibil cu <code>p</code>, atunci se va afișa <code>0</code>.

= Restricții și precizări =

* <code>1 ≤ a , b , c ≤ 1.000.000.000</code>
* <code>a ≥ b + c</code>
* <code>2 ≤ p ≤ 1.000</code>

= 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 <code>p</code> ( Numărul  reprezintă combinări de  elemente luate câte  ).

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

În exemplul dat avem , deci exponentul este <code>3</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
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()

</syntaxhighlight>