Într-o cutie sunt n bomboane.

Într-o cutie sunt n bomboane.
Dacă se împart cele n bomboane în mod egal la un grup de p copii, rămân p-1 bomboane.
Dacă se împart cele n bomboane în mod egal la un grup de q copii, rămân q-1 bomboane.

Cerința

Se dau p și q, numere naturale. Aflați cel mai mic n, număr natural care satisface condițiile de mai sus.

Date de intrare

Fișierul de intrare bomboane4.in conține pe prima linie numerele p și q.

Date de ieșire

Programul afișează în fișierul bomboane4.out numărul n.

Restricții și precizări

• 1 ≤ p ≤ 1018
• 1 ≤ q ≤ 1018

Exemplul 1

bomboane4.in

4 7

bomboane4.out

27

Explicație

27 = 4 * 6 + 3. Dacă se împart 27 de bomboane la 4 copii, aceștia primesc câte 6 bomboane și rămân 3 bomboane.
27 = 7 * 3 + 6. Dacă se împart 27 de bomboane la 7 copii, aceștia primesc câte 3 bomboane și rămân 6 bomboane.

Exemplul 2

bomboane4.in

10 20

bomboane4.out

19

Explicație

19 = 1 * 10 + 9. Dacă se împart 19 bomboane la 10 copii, aceștia primesc câte o bomboană și rămân 9 bomboane.
19 = 0 * 20 + 19. Dacă se împart 19 bomboane la 20 copii, aceștia primesc câte 0 bomboane și rămân 19 bomboane.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("bomboane4.in");
ofstream cout("bomboane4.out");

int A[30] , B[30] , C[50];

long long int cmmdc(long long int a , long long int b)
{
    while(b)
    {
        long long int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void inmultire()
{
    int i,j,T=0;
    C[0]=A[0]+B[0]-1;
    for (i=1;i<=A[0]+B[0];)
        C[i++]=0;
    for (i=1;i<=A[0];i++)
        for (j=1;j<=B[0];j++)
            C[i+j-1]+=A[i]*B[j];
    for (i=1;i<=C[0];i++)
    {
        T=(C[i]+=T)/10;
        C[i]%=10;
    }
    if( T )
        C[++C[0]]=T;
}


unsigned long Divide(unsigned long long X)
{ int i;

  unsigned long R=0;

  for (i=C[0];i;i--)

    { C[i]=(R=10*R+C[i])/X;

      R%=X;

    }

  while (!C[C[0]] && C[0]>1) C[0]--;

  return R;

}

void Subtract()
{
    int S[50];
    int i, T=0;
    S[0]=1 , S[1]=1;
    for (i=S[0]+1;i<=C[0];) S[i++]=0;

    for (i=1;i<=C[0];i++)

    C[i]+= (T=(C[i]-=S[i]+T)<0) ? 10 : 0;

    while (!C[C[0]]) C[0]--;

}

int main()
{
    long long int a , b;
    cin >> a >> b;
    unsigned long long d = cmmdc(a , b);
    int i = 1;
    while(a)
    {
        A[i]=a%10;
        a/=10;
        i++;
    }
    A[0]=i-1;
    i = 1;
    while(b)
    {
        B[i]=b%10;
        b/=10;
        i++;
    }
    B[0]=i-1;
    inmultire();
    int x = Divide(d);
    Subtract();
    for(int i = C[0] ; i ; --i)
        cout << C[i];
}