Intermediate.
Put your skills to the test.

Problem summary

Cut each of m identical oranges into the same number of equal pieces, then distribute all pieces equally among n guests. Minimize the pieces cut from each orange.

Constraints

1 ≤ n,m ≤ 10^9.

Worked example

Input and output for the worked example discussed below.

2 5

2

Solution analysis

1. If every orange is cut into x pieces, there are mx pieces in total. Equal distribution is possible exactly when n divides mx.
2. Let g=gcd(n,m), n=gn′ and m=gm′. The condition becomes n′ dividing m′x. Since n′ and m′ are coprime, this is equivalent to n′ dividing x. The smallest positive choice is therefore n/g.
3. For two guests and five oranges, gcd(2,5)=1, so each orange needs two pieces. For two guests and four oranges, the gcd is 2 and x=1: whole oranges can already be shared equally.

Why it works

Reducing by the gcd removes all factors of n already supplied by m. The remaining factor n/g must divide x because it is coprime to m/g. Choosing x=n/g satisfies the condition and no smaller positive x can.

Watch out. The task asks for pieces per orange, not pieces per person. All oranges use the same cut count. Return 1 when no cutting is needed, not 0.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
    long long guests;
    long long oranges;
    cin>>guests>>oranges;
    // Only the denominator remaining after gcd reduction must be supplied by cuts.
    cout<<guests/gcd(guests,oranges)<<'\n';
}