Euclidean Algorithm

The Euclidean algorithm is an efficient method for finding the greatest common divisor (GCD) of two integers.

How It Works

1. Divide the larger number by the smaller number and find the remainder.
2. Replace the larger number with the smaller number, and the smaller number with the remainder.
3. Repeat the process until the remainder is zero.
4. The last non-zero remainder is the GCD.

Example Problem: Minimum Cuts to Share Sausages

COCI 2013/2014 — KUŠAČ

Problem Summary

At a food festival, N sausages must be divided equally among M tasters. The goal is to calculate the minimum number of cuts needed to ensure each taster gets the same amount of sausage.

For example:

• With 2 sausages and 6 tasters, you can cut each sausage into 3 equal pieces using a total of 4 cuts.
• With 3 sausages and 4 tasters, cut a quarter off each sausage: 3 cuts in total.

The problem asks:

Given $N$ sausages and $M$ tasters, what is the minimum number of cuts required?

Solution Explained

The key idea is that the minimum number of cuts is directly related to the greatest common divisor (GCD) of $N$ and $M$.

• If $N$ and $M$ share common divisors, fewer cuts are needed.
• The formula is simple: $\text{Minimum cuts}=M-gcd(N,M)$

This works because the GCD tells us how many evenly divisible sections we can create without unnecessary cuts.

Solution Code (C++)

#include <iostream>
using namespace std;
 
int gcd(int A, int B) {
  return B ? gcd(B, A % B) : A;
}
 
void solve(void) {
  int N, M; cin >> N >> M;
 
  cout << M - gcd(N, M);
}
 
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  solve();
  return 0;
}