If there is an efficient procedure for extracting common factors, apply it to the original polynomial and its derivative to obtain the factors that are common to both. If the original polynomial contains qn, the polynomial and its derivative both contain the common factor qn-1. Use this procedure to find the factors that have multiplicity > 1; rather like pulling 7 out of 72×5.
If the polynomials over R exhibit unique factorization, we can be more precise. We already know the derivative includes sn-1 when p(x) includes sn. Let both p and p′ include sn-1, where s is an irreducible polynomial. We know that p does not include sn+1, else p and p′ would both include sn. Suppose p contains fewer than n instances of s. We'll illustrate with n-1. Write p as q×sn-1 and apply the product rule. We must account for n-1 factors of s, hence s divides q×s′. Since s′ has a smaller degree than s, s divides q. Thus our original polynomial p(x) has exactly n factors of s.
This is fine when R has characteristic 0, but we can get in trouble in characteristic n. If p′ drops to 0, all bets are off. Even if p′ is nonzero, our proof is derailed if s′ = 0. Recall the point in the proof where we showed s divides q×s′, hence s divides q; this fails if s′ is 0.
If R is the integers mod p, we don't really have to worry about s′ = 0. If all the exponents on s are multiples of p then s is not irreducible. In fact it is some other polynomial t(x) raised to the p power. Therefore some exponent on s is not divisible by p, and s′ is nonzero.