Dado un entero positivo N , la tarea es encontrar el conteo de todos los números M tales que cuando el número N se divide por M , el cociente es igual a su resto, es decir (⌊N/M⌋ = N mod M) donde ⌊ ⌋ denota el valor mínimo de un número dado.
Ejemplos:
Entrada: N = 8
Salida: 2
Explicación: Cuando 8 se divide por 3 y 7, devuelve el mismo Cociente y Resto.
8 / 3 = 8 % 3, 8 / 7 = 8 % 7. Por lo tanto, la respuesta requerida es 2.Entrada: N = 1000000000000
Salida: 84
Enfoque ingenuo: el enfoque más simple se basa en el hecho de que M no puede ser mayor que N , ya que para cualquier número mayor que N , el cociente sería cero. Mientras que su módulo con N siempre será N . Por lo tanto, repita todos los números del 1 al N y cuente todos los números que satisfagan la condición dada.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: la idea óptima se basa en la observación que se indica a continuación:
Si (⌊N/M⌋ = N mod M) , entonces M + 1 debe ser un divisor de N .
Prueba de la observación:
Si ⌊N/M⌋ = N mod M , entonces sea N / M igual a K .
Por lo tanto, N debe ser igual a K * M + K ya que K es tanto el cociente como el resto.
N = K * M + K
N = K * (M + 1)
Por lo tanto, para que M esté en nuestro conjunto de respuestas, es necesario que M + 1 sea un divisor de N .
Tenga en cuenta que M + 1 debe ser un divisor de N es una condición necesaria pero no suficiente para ⌊N/M⌋ = N mod M .
Siga los pasos a continuación para resolver el problema:
- Encuentre todos los divisores de N y guárdelos en una array. Esto se puede calcular en complejidad O(√ N).
- Verifique todos los divisores iterando a través de la array , y si el divisor menos 1 satisface la condición dada ⌊N / M⌋ = N mod M , aumente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// count of numbers such that it
// gives same quotient and remainder
void countDivisors(long long int n)
{
int count = 0;
// Stores divisor of number N.
vector<long long int> divisor;
// Iterate through numbers from 2
// to sqrt(N) and store divisors of N
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i)
divisor.push_back(i);
else {
divisor.push_back(i);
divisor.push_back(n / i);
}
}
}
// As N is also divisor of itself
divisor.push_back(n);
// Iterate through divisors
for (auto x : divisor) {
x -= 1;
// Checking whether x satisfies the
// required condition
if ((n / x) == (n % x))
count++;
}
// Print the count
cout << count;
}
// Driver Code
int main()
{
// Given N
long long int N = 1000000000000;
// Function Call
countDivisors(N);
return 0;
}
Java
// Java program of the above approach
class GFG {
// Function to calculate the
// count of numbers such that it
// gives same quotient and remainder
static void countDivisors(int n)
{
int count = 0;
int j = 0;
// Stores divisor of number N.
int divisor[] = new int[n];
// Iterate through numbers from 2
// to sqrt(N) and store divisors of N
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i){
divisor[j] = i;
j += 1;
}
else {
divisor[j] = i;
divisor[j + 1] = n / i;
j += 2;
}
}
}
// As N is also divisor of itself
divisor[j] = n;
// Iterate through divisors
for (int i = 0; i <= j; i++)
{
int x = divisor[i];
x -= 1;
// Checking whether x satisfies the
// required condition
if ((n / x) == (n % x))
count++;
}
// Print the count
System.out.print(count);
}
// Driver Code
public static void main (String[] args)
{
// Given N
int N = 10000000;
// Function Call
countDivisors(N);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program of the above approach from math import floor, sqrt # Function to calculate the # count of numbers such that it # gives same quotient and remainder def countDivisors(n): count = 0 # Stores divisor of number N. divisor = [] # Iterate through numbers from 2 # to sqrt(N) and store divisors of N for i in range(2, floor(sqrt(n))): if (n % i == 0): if (n // i == i): divisor.append(i) else: divisor.append(i) divisor.append(n // i) # As N is also divisor of itself divisor.append(n) # Iterate through divisors for x in divisor: x -= 1 # Checking whether x satisfies the # required condition if ((n // x) == (n % x)): count += 1 # Print the count print(count) # Driver Code if __name__ == '__main__': # Given N N = 1000000000000 # Function Call countDivisors(N) # This code is contributed by mohit kumar 29
C#
// C# program of the above approach
using System;
class GFG {
// Function to calculate the
// count of numbers such that it
// gives same quotient and remainder
static void countDivisors(int n)
{
int count = 0;
int j = 0;
// Stores divisor of number N.
int []divisor = new int[n];
// Iterate through numbers from 2
// to sqrt(N) and store divisors of N
for (int i = 2; i <= Math.Sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i){
divisor[j] = i;
j += 1;
}
else {
divisor[j] = i;
divisor[j + 1] = n / i;
j += 2;
}
}
}
// As N is also divisor of itself
divisor[j] = n;
// Iterate through divisors
for (int i = 0; i <= j; i++)
{
int x = divisor[i];
x -= 1;
// Checking whether x satisfies the
// required condition
if ((n / x) == (n % x))
count++;
}
// Print the count
Console.Write(count);
}
// Driver Code
public static void Main(String[] args)
{
// Given N
int N = 10000000;
// Function Call
countDivisors(N);
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// Javascript program of the above approach
// Function to calculate the
// count of numbers such that it
// gives same quotient and remainder
function countDivisors(n)
{
var count = 0;
var j = 0;
// Stores divisor of number N.
var divisor = Array(n).fill(0);
// Iterate through numbers from 2
// to sqrt(N) and store divisors of N
for (var i = 2; i <= Math.sqrt(n); i++)
{
if (n % i == 0) {
if (parseInt(n / i) == i)
{
divisor[j] = i;
j += 1;
} else {
divisor[j] = i;
divisor[j + 1] = parseInt(n / i);
j += 2;
}
}
}
// As N is also divisor of itself
divisor[j] = n;
// Iterate through divisors
for (var i = 0; i <= j; i++) {
var x = divisor[i];
x -= 1;
// Checking whether x satisfies the
// required condition
if (parseInt(n / x) == parseInt(n % x))
count++;
}
// Print the count
document.write(count);
}
// Driver Code
// Given N
var N = 10000000;
// Function Call
countDivisors(N);
// This code contributed by aashish1995
</script>
84
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(sqrt(N))