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

<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>