La respuesta es N – N / K + N / K² – N / K³ …
Aquí está mi solución:
int MFS(int N,int K) { int ret=0; for(int i=1;N;i=-i) { ret+=N*i; N/=K; } return ret; }
Entonces, ¿cómo funciona esto? Comencemos con el conjunto completo {1 … N}. Necesitamos eliminar algunos números de esto para que sea un conjunto libre K-múltiple. Para esto, eliminemos cada múltiplo de K del conjunto. Estos son los números K, 2K … y hay N / K de ellos. Eliminarlos nos da un conjunto libre de K-múltiples. Pero hemos eliminado algunos números innecesariamente. Como ya eliminamos K, eliminar K² fue innecesario. Por lo tanto, podemos volver a colocar K², 2K² …, que serían N / K² en total. Pero esto termina colocando tanto K² como K³ en el set y ahora necesitamos eliminar todos los múltiplos de K³. Procediendo de esta manera, es fácil ver que la cardinalidad del conjunto final es N – N / K + N / K² – N / K³ …
En general, un tamaño de entrada de N = 10⁹ en un problema matemático debería darle la idea de que ni el tiempo ni la complejidad espacial de la solución pueden ser O (N) y que tiene que encontrar algún tipo de solución de forma cerrada.
- La secuencia de números no cuadrados que no son cuadrados perfectos, es decir, 2,3,5,6,7,8,10 … se puede obtener mediante la fórmula F (n) = n + piso (0.5 + sqrt (n)). ¿Cómo probamos esto?
- ¿Cuál es el algoritmo más eficiente para averiguar si un entero es divisible por 7?
- ¿Cómo entiendo este código de número primo más grande?
- ¿Cómo encuentro todos los pares de enteros cuyo producto es menor que igual a un número particular?
- ¿Cuáles son los requisitos matemáticos para comenzar a estudiar el programa Langlands?