Número de divisor

Question

¿Cómo encontrar el número de divisores de un número 'n' que también son divisibles por otro número 'k' sin pasar por todos los divisores de n? He intentado lo siguiente:

Almacenó las potencias de todos los factores primos de n en una matriz asociativa A e hizo lo mismo para k, almacenando las potencias de todos los factores primos en la matriz B.

    ans = 1
    for a in A:    // Here a is the prime factor and A[a] gives its power
        ans *= if( a is present in B ) ? 1 : A[a] + 1
    print ans

Nota: No es una tarea.

Answer 1

Cualquier divisor de $n$ que a su vez es divisible por $k$ puede escribirse como $d k$ , donde $d$ es un divisor de $\frac nk$ . Por lo tanto, su número es exactamente el número de divisores de $\frac nk$ .

Por supuesto que necesitamos $k$ para ser un divsor de $n$ para que esto tenga algún sentido.

Answer 2

Todo lo que tienes que hacer es calcular $\sigma_0(n/k)$ , donde $\sigma_0(m)$ es la función divisor, que cuenta el número de divisores de $m$ . La razón de esto es que $$ k \, | \, m \, | \, n \quad \Longleftrightarrow \quad m = kd \quad \text{and} \quad d \, | \, n/k. $$ Esto es bastante fácil de demostrar, lo dejaré a tu criterio. Ahora a calcular $\sigma_0(n/k)$ se puede demostrar que $\sigma$ es una función multiplicativa, porque $f(n) = 1$ es multiplicativo, por lo que $$ \sigma_0(n) = \sum_{d \, | \, n} f(d) $$ también es (teorema bien conocido en teoría de números que $\sum_{d \, | \, n} f(d)$ es multiplicativo cuando $f$ es). Por lo tanto, ya que $\sigma_0(p^{\alpha}) = \alpha+1$ , usted tiene $$ \sigma_0(n) = \prod_{p \, | , n} (\alpha(n,p) + 1) $$ donde $\alpha(n,p)$ representa el mayor poder de $p$ dividiendo $n$ . En otras palabras, todo lo que tienes que hacer es el factor $n/k$ y utilizar la factorización para calcular $\sigma_0(n/k)$ .

Espero que eso ayude,