Рубрики

Минимальное целое число такое, что оно оставляет остаток 1 при делении на любой элемент из диапазона [2, N]

Для заданного целого числа N задача состоит в том, чтобы найти минимально возможное целое число X, такое, что X% M = 1 для всех M из диапазона [2, N]

Примеры:

Input: N = 5
Output: 61
61 % 2 = 1
61 % 3 = 1
61 % 4 = 1
61 % 5 = 1

Input: N = 2
Output: 3

Подход: найдите lcm всех целых чисел из диапазона [2, N] и сохраните его в переменной lcm . Теперь мы знаем, что lcm — это наименьшее число, которое делится на все элементы из диапазона [2, N], и чтобы оно оставляло остаток от 1 на каждом делении, просто добавьте 1 к нему, т.е. lcm + 1 — требуемый ответ ,

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата наименьшего числа
// который при делении на любой элемент из
// диапазон [2, N] оставляет остаток от 1

long getMinNum(int N)

{

    // Находим LCM элементов

    // из диапазона [2, N]

    int lcm = 1;

    for (int i = 2; i <= N; i++)

        lcm = ((i * lcm) / (__gcd(i, lcm)));

  

    // Возвращаем нужный номер

    return (lcm + 1);

}

  
// Код драйвера

int main()

{

    int N = 5;

  

    cout << getMinNum(N);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG {

  

    // Функция для возврата наименьшего числа

    // который при делении на любой элемент из

    // диапазон [2, N] оставляет остаток от 1

    static long getMinNum(int N)

    {

        // Находим LCM элементов

        // из диапазона [2, N]

        int lcm = 1;

        for (int i = 2; i <= N; i++)

            lcm = ((i * lcm) / (__gcd(i, lcm)));

  

        // Возвращаем нужный номер

        return (lcm + 1);

    }

  

    static int __gcd(int a, int b)

    {

        if (b == 0)

            return a;

        return __gcd(b, a % b);

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int N = 5;

        System.out.println(getMinNum(N));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

from math import gcd

  
# Функция для возврата наименьшего числа
# который при делении на любой элемент из
# диапазон [2, N] оставляет остаток от 1

def getMinNum(N) : 

  

    # Найти LCM элементов

    # из диапазона [2, N]

    lcm = 1

    for i in range(2, N + 1) :

        lcm = ((i * lcm) // (gcd(i, lcm))); 

  

    # Вернуть нужный номер

    return (lcm + 1); 

  

  
# Код драйвера

if __name__ == "__main__"

  

    N = 5

  

    print(getMinNum(N)); 

  
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;

  

class GFG {

  

    // Функция для возврата наименьшего числа

    // который при делении на любой элемент из

    // диапазон [2, N] оставляет остаток от 1

    static long getMinNum(int N)

    {

        // Находим LCM элементов

        // из диапазона [2, N]

        int lcm = 1;

        for (int i = 2; i <= N; i++)

            lcm = ((i * lcm) / (__gcd(i, lcm)));

  

        // Возвращаем нужный номер

        return (lcm + 1);

    }

  

    static int __gcd(int a, int b)

    {

        if (b == 0)

            return a;

        return __gcd(b, a % b);

    }

  

    // Код драйвера

    public static void Main()

    {

        int N = 5;

        Console.WriteLine(getMinNum(N));

    }

}

  
// Этот код предоставлен anuj_67 ..

PHP

<?php
// PHP реализация подхода

  
// Функция для возврата наименьшего числа
// который при делении на любой элемент из
// диапазон [2, N] оставляет остаток от 1

function getMinNum($N)

{

    // Находим LCM элементов

    // из диапазона [2, N]

    $lcm = 1;

    for ($i = 2; $i <= $N; $i++)

        $lcm = (($i * $lcm) / (__gcd($i, $lcm)));

  

    // Возвращаем нужный номер

    return ($lcm + 1);

}

  

function __gcd($a, $b)

{

    if ($b == 0)

        return $a;

    return __gcd($b, $a % $b);

}

  
// Код драйвера

  

$N = 5;

echo (getMinNum($N));

      
// Этот код предоставлен ajit ....
?>

Выход:

61

Рекомендуемые посты:

Минимальное целое число такое, что оно оставляет остаток 1 при делении на любой элемент из диапазона [2, N]

0.00 (0%) 0 votes