55. Подарки к 8 Марта

 

На праздник 8-го Марта ребята решили сделать подарок девушкам. Готовя подарки, они быстро разложили в подарки по открытке, мягкой игрушке. А когда начали раскладывать мандарины, то попали в затруднительное положение. Сначала они разложили мандарины по m штук в каждый пакет (а в другие пакеты – яблоки), не вышло: на один из пакетов пришелся m – 1 мандарин. Когда попробовали положить по m – 1 мандарину, то осталось m – 2 мандарина. Когда попробовали положить по m – 2 мандарина, то осталось m – 3, и т.д. Когда попробовали положить по 2 мандарина, то оставался 1 мандарин. Какое же количество мандарин купили ребята?

 

Вход. Количество мандарин m (1 < m ≤ 1000), которое хотели ребята вначале положить в подарок.

 

Выход. Наименьшее возможное количество мандарин, которое купили ребята в подарок девушкам.

 

Пример входа

Пример выхода

4

11

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Ответом на задачу будет значение a = НОК(1, 2, 3, …, m) – 1. При делении числа a на i (2 ≤ i ≤ m) в остатке будет i – 1, как и требуется в условии задачи.

Занесем все числа от 1 до m в массив t. Покажем, как вычислить a = НОК(t1, t2, …, tn), совершив минимум операций над большими числами (значение а является большим). Переберем все пары (ti, tj), i < j, для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.

 

Реализация алгоритма

Прочитаем значение m и занесем в i-ую ячейку  массива t число i.

 

scanf("%d",&m);

for(i = 1; i <= m; i++) t[i] = i;

 

После выполнения следующего двойного цикла НОК(1, 2, 3, …, m) равно произведению чисел в массиве t. Функция gcd вычисляет наибольший общий делитель двух чисел.

 

for(i = 1; i <= m; i++)

for(j = i+1; j <= m; j++)

{

  d = gcd(t[i],t[j]);

  t[j] /= d;

}

 

Вычисляем произведение чисел в массиве t, используя длинную арифметику.

 

a = BigInteger(t[1]);

for(i = 1; i <= m; i++) a = a * t[i];

 

Вычитаем из a единицу и выводим результат.

 

a--; a.print();printf("\n");

 

Java реализация

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

 

    BigInteger res = BigInteger.ONE;

    for(int i = 1; i <= n; i++)

    {

      BigInteger x = BigInteger.valueOf(i);

      // res = res * x / gcd(res,x)

      res = res.multiply(x).divide(res.gcd(x));

    }

    res = res.subtract(BigInteger.ONE);  

 

    System.out.println(res);

    con.close();

  }

}

 

Java реализация – длинное умножение

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static int gcd(int a, int b)

  {

    return (b == 0) ? a : gcd(b,a % b);

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int m = con.nextInt();

    int t[] = new int[m+1];

    for(int i = 1; i <= m; i++)

      t[i] = i;

   

    for(int i = 1; i <= m; i++)

    for(int j = i + 1; j <= m; j++)

    {

      int d = gcd(t[i],t[j]);

      t[j] /= d;

    }

   

    BigInteger res = BigInteger.ONE;

    for(int i = 1; i <= m; i++)

      res = res.multiply(BigInteger.valueOf(t[i]));

    res = res.subtract(BigInteger.ONE);  

 

    System.out.println(res);

    con.close();

  }

}