UVA 11246- Conjunto libre múltiple: ¿Cómo resolverlo sin listas?

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.