Hydratation – Qualification 2012

Énoncé¶

En salle machine, il fait souvent très chaud, c'est pourquoi nous abreuvons nos candidats. Par souci de précision, nous leur permettons même de demander le nombre de centilitres de jus d'orange qu'ils souhaitent. Hélas, bien que nous ayons une quantité infinie de jus d'orange, nous ne disposons que de deux gobelets, respectivement de a et b centilitres (a < b).

Vous pouvez :

• remplir un gobelet à ras bord de jus d'orange ;
• vider un gobelet intégralement ;
• verser un gobelet dans un autre jusqu'à ce que l'un soit vide ou que l'autre soit plein.

Combien de commandes différentes comprises entre 1 et b centilitres pouvons-nous satisfaire ?

Contraintes¶

• 1 <= a < b <= 999 999 999 sont les contenances de nos gobelets, en centilitres.

Entrée¶

L'entrée standard contient deux entiers a et b (dans cet ordre) représentant les contenances de nos gobelets, en centilitres.

Sortie¶

Vous devez écrire une ligne sur la sortie standard : le nombre de commandes différentes comprises entre 1 et b centilitres que nous pouvons satisfaire.