Найдите все возможные остатки от деления N на все положительные целые числа от 1 до N + 1.

Опубликовано: 2 Января, 2022

Учитывая большое целое число N , задача состоит в том, чтобы найти все возможные остатки, когда N делится на все положительные целые числа от 1 до N + 1 .

Примеры:

Input: N = 5
Output: 0 1 2 5
5 % 1 = 0
5 % 2 = 1
5 % 3 = 2
5 % 4 = 1
5 % 5 = 0
5 % 6 = 5
Input: N = 11
Output: 0 1 2 3 5 11

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: запустить цикл от 1 до N + 1 и вернуть все уникальные остатки, найденные при делении N на любое целое число из диапазона. Но этот подход неэффективен для больших значений N.

Эффективный подход: можно заметить, что одна часть ответа всегда будет содержать числа от 0 до ceil (sqrt (n)) . Это можно доказать, запустив наивный алгоритм на меньших значениях N и проверив полученные остатки, или решив уравнение ceil (N / k) = x или x ≤ (N / k) <x + 1, где x - одно из остатки для всех целых чисел k при делении N на k для k от 1 до N + 1 .
Решением указанного неравенства является не что иное, как целые числа k из (N / (x + 1), N / x] длины N / x - N / (x + 1) = N / (x ² + x) . Следовательно, выполнить итерацию от k = 1 до ceil (sqrt (N)) и сохранить все уникальные N% k . Что, если указанное выше k больше ceil (sqrt (N)) ? Они всегда будут соответствовать значениям 0 ≤ x <ceil ( sqrt (N)) . Итак, снова начните сохранять остатки от N / (ceil (sqrt (N)) - от 1 до 0 и верните окончательный ответ со всеми возможными остатками.

Ниже представлена реализация описанного выше подхода:

C ++

 // 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

 # 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 #

 // 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

Выход:

0 1 2 5

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Язык программирования Олимпиады по программированию Алгоритмы

Найдите все возможные остатки от деления N на все положительные целые числа от 1 до N + 1.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

Джава

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ