Cake from Tolya (Editorial)

Let us represent the cake as a line segment of some length. Mark the cuts corresponding to dividing it into $n$ equal parts. Then mark the cuts corresponding to dividing it into $m$ equal parts. Making all these cuts will give us exactly the required partition. It remains to count the number of resulting pieces. This number is:

Proof. Dividing the cake into $n$ equal parts requires n - 1 cuts. Similarly, dividing it into $m$ parts requires m - 1 cuts. Among them, there will be GCD(n, m) - 1 coinciding cuts. Therefore, the total number of distinct cuts is

After making these cuts, the cake will be divided into n + m - GCD(n, m) pieces.

Example

When cutting the cake into $6$ pieces, $5$ cuts are required.

When cutting the cake into $9$ pieces, $8$ cuts are required.

Among them, GCD(6, 9) - 1 = 2 cuts coincide.

Thus, the cake will have 5 + 8 - 2 = 11 distinct cuts. After making them, the cake will be divided into $12$ pieces.

Algorithm implementation

The function gcd computes the greatest common divisor of the numbers $a$ and $b$.

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

The main part of the program. Read the input data.

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

Compute and print the answer.

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

Java implementation

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 implementation

The function gcd computes the greatest common divisor of the numbers $a$ and $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)

The main part of the program. Read the input data.

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

Compute and print the answer.

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