Торт від Толі (Розбір)

Уявімо торт у вигляді відрізка певної довжини. Позначимо на ньому розрізи, що відповідають поділу на $n$ рівних частин. Потім позначимо розрізи, що утворюються при поділі на $m$ рівних частин. Зробивши всі ці розрізи, ми отримаємо саме те розбиття, яке потрібно. Залишилося підрахувати кількість отриманих частин. Воно дорівнює:

Доведення. При поділі торта на $n$ рівних частин потрібно n - 1 розріз. Аналогічно, для $m$ частин — m - 1 розріз. Серед них виявиться НСД(n, m) - 1 збігаючих розрізів. Отже, всього буде зроблено

різних розрізів. Після цього торт розділиться на n + m - НСД(n, m) частин.

Приклад

При розрізанні торта на $6$ частин потрібно $5$ розрізів.

При розрізанні торта на $9$ частин потрібно $8$ розрізів.

З них збігаються НСД(6, 9) - 1 = 2 розрізи.

Таким чином, на торті вийде 5 + 8 - 2 = 11 різних розрізів. Після їх виконання торт розділиться на $12$ шматків.

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

Функція gcd обчислює найбільший спільний дільник двох чисел $a$ і $b$.

int gcd(int a, int b)
{
  return (!b) ? a : gcd(b,a % b);
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&m,&n);

Вичисляємо і виводимо відповідь.

res = m + n - gcd(m,n);
printf("%d\n",res);

Java реалізація

import java.util.*;

public class Main
{

  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 n = con.nextInt();

    int res = m + n - gcd(m,n);
    System.out.println(res);
    con.close();
  }
}    

Python реалізація

Функція gcd обчислює найбільший спільний дільник двох чисел $a$ і $b$.

def gcd(a, b):
  if a == 0: return b
  if b == 0: return a
  if a > b: return gcd(a % b, b)
  return gcd(a, b % a)

Основна частина програми. Читаємо вхідні дані.

m, n = map(int, input().split())

Витисляємо і виводимо відповідь.

res = m + n - gcd(m, n)
print(res)