Encuentre todos los restos posibles cuando N se divide por todos los números enteros positivos de 1 a N+1

Dado un número entero grande N , la tarea es encontrar todos los restos posibles cuando N se divide por todos los números enteros positivos de 1 a N + 1 .

Ejemplos: 

Entrada: N = 5 
Salida: 0 1 2 5 
5 % 1 = 0 
5 % 2 = 1 
5 % 3 = 2 
5 % 4 = 1 
5 % 5 = 0 
5 % 6 = 5

Entrada: N = 11 
Salida: 0 1 2 3 5 11 
 

Enfoque ingenuo: Ejecute un ciclo de 1 a N + 1 y devuelva todos los restos únicos encontrados al dividir N por cualquier número entero del rango. Pero este enfoque no es eficiente para valores más grandes de N.

Enfoque eficiente: se puede observar que una parte de la respuesta siempre contendrá números entre 0 y ceil(sqrt(n)) . Puede probarse ejecutando el algoritmo ingenuo en valores más pequeños de N y comprobando los residuos obtenidos o resolviendo la ecuación ceil(N / k) = x o x ≤ (N / k) < x + 1 donde x es uno de los restos de todos los enteros k cuando N se divide por k para k de 1 a N + 1 . 
La solución a la desigualdad anterior no es más que números enteros k de(N / (x + 1), N / x] de longitud N / x – N / (x + 1) = N / (x ² + x) . Por lo tanto, iterar desde k = 1 hasta ceil(sqrt(N) ) y almacene todos los N % k únicos . ¿Qué pasa si el k anterior es mayor que ceil(sqrt(N)) ? Siempre corresponderán a los valores 0 ≤ x < ceil(sqrt(N)) . Entonces, nuevamente comience a almacenar los residuos from N / (ceil(sqrt(N)) – 1 a 0 y devuelve la respuesta final con todos los restos posibles.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
 
// Function to find all the distinct
// remainders when n is divided by
// all the elements from
// the range [1, n + 1]
void findRemainders(ll n)
{
 
    // Set will be used to store
    // the remainders in order
    // to eliminate duplicates
    set<ll> vc;
 
    // Find the remainders
    for (ll i = 1; i <= ceil(sqrt(n)); i++)
        vc.insert(n / i);
    for (ll i = n / ceil(sqrt(n)) - 1; i >= 0; i--)
        vc.insert(i);
 
    // Print the contents of the set
    for (auto it : vc)
        cout << it << " ";
}
 
// Driver code
int main()
{
    ll n = 5;
 
    findRemainders(n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to find all the distinct
// remainders when n is divided by
// all the elements from
// the range [1, n + 1]
static void findRemainders(long n)
{
 
    // Set will be used to store
    // the remainders in order
    // to eliminate duplicates
    HashSet<Long> vc = new HashSet<Long>();
 
    // Find the remainders
    for (long i = 1; i <= Math.ceil(Math.sqrt(n)); i++)
        vc.add(n / i);
    for (long i = (long) (n / Math.ceil(Math.sqrt(n)) - 1);
                                                i >= 0; i--)
        vc.add(i);
 
    // Print the contents of the set
    for (long it : vc)
        System.out.print(it+ " ");
}
 
// Driver code
public static void main(String[] args)
{
    long n = 5;
 
    findRemainders(n);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
from math import ceil, floor, sqrt
 
# Function to find all the distinct
# remainders when n is divided by
# all the elements from
# the range [1, n + 1]
def findRemainders(n):
 
    # Set will be used to store
    # the remainders in order
    # to eliminate duplicates
    vc = dict()
 
    # Find the remainders
    for i in range(1, ceil(sqrt(n)) + 1):
        vc[n // i] = 1
    for i in range(n // ceil(sqrt(n)) - 1, -1, -1):
        vc[i] = 1
 
    # Print the contents of the set
    for it in sorted(vc):
        print(it, end = " ")
 
# Driver code
n = 5
 
findRemainders(n)
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find all the distinct
// remainders when n is divided by
// all the elements from
// the range [1, n + 1]
static void findRemainders(long n)
{
 
    // Set will be used to store
    // the remainders in order
    // to eliminate duplicates
    List<long> vc = new List<long>();
 
    // Find the remainders
 
    for (long i = 1; i <= Math.Ceiling(Math.Sqrt(n)); i++)
        vc.Add(n / i);
    for (long i = (long) (n / Math.Ceiling(Math.Sqrt(n)) - 1);
                                                 i >= 0; i--)
        vc.Add(i);
    vc.Reverse();
     
    // Print the contents of the set
    foreach (long it in vc)
        Console.Write(it + " ");
}
 
// Driver code
public static void Main(String[] args)
{
    long n = 5;
 
    findRemainders(n);
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
 
// Function to find all the distinct
// remainders when n is divided by
// all the elements from
// the range [1, n + 1]
function findRemainders(n)
{
     
    // Set will be used to store
    // the remainders in order
    // to eliminate duplicates
    var vc = new Set();
 
    // Find the remainders
    for(var i = 1; i <= Math.ceil(Math.sqrt(n)); i++)
        vc.add(parseInt(n / i));
    for(var i = parseInt(n / Math.ceil(Math.sqrt(n))) - 1;
            i >= 0; i--)
        vc.add(i);
 
    // Print the contents of the set
    [...vc].sort((a, b) => a - b).forEach(it => {
        document.write(it + " ");
    });
}
 
// Driver code
var n = 5;
 
findRemainders(n);
 
// This code is contributed by famously
 
</script>

0 1 2 5

Complejidad del tiempo: O(sqrt(n))

Espacio auxiliar: O(sqrt(n))