Tolyadan Tort (Həll təhlili)

Tortu müəyyən uzunluğu olan bir kəsik olaraq təsəvvür edək. Bu kəsiyin üzərində onu $n$ bərabər hissəyə bölən kəsikləri qeyd edək. Daha sonra onu $m$ bərabər hissəyə bölən kəsikləri qeyd edək. Bütün bu kəsikləri etdikdən sonra istədiyimiz bölünməni alarıq. Qalan yalnız yaranmış parçaların sayını hesablamaqdır. Bu say:

Sübut. Tortu $n$ bərabər hissəyə bölmək üçün n - 1 kəsik etmək lazımdır. Eyni şəkildə, $m$ hissələr üçün də m - 1 kəsik lazımdır. Bu kəsiklər arasında ƏBOB(n, m) - 1 təsadüfi kəsiklər olacaq. Buna görə də, ümumi olaraq bu qədər kəsik ediləcək

fərqli kəsiklər. Bundan sonra tort n + m - ƏBOB(n, m) hissəyə bölünəcək.

Nümunə

Tortu $6$ hissəyə bölmək üçün $5$ kəsik lazımdır.

Tortu $9$ hissəyə bölmək üçün $8$ kəsik lazımdır.

Bu kəsiklərdən ƏBOB(6, 9) - 1 = 2 kəsik təsadüf edir.

Beləliklə, tortun üzərində 5 + 8 - 2 = 11 fərqli kəsik olacaq. Bu kəsiklərdən sonra tort $12$ parçaya bölünəcək.

Alqoritmin implementasiyası

gcd funksiyası iki ədədin $a$ və $b$ ən böyük ortaq bölənini hesablayır.

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

Proqramın əsas hissəsi. Giriş məlumatını oxuyuruq.

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

Nəticəni hesablayır və çıxışa veririk.

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

Java implementasiyası

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 implementasiyası

gcd funksiyası iki ədədin $a$ və $b$ ən böyük ortaq bölənini hesablayır.

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)

Proqramın əsas hissəsi. Giriş məlumatını oxuyuruq.

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

Nəticəni hesablayır və çıxışa veririk.

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