| UFPE Starters Final Try-Outs 2026 |
|---|
| Finished |
In Miguel's beach house, there is a magic room: whoever solves the room's riddle is granted a wish. Noticing that his friend Walfrido was sad, Thawan decided to enter the room to cheer him up. His goal is to ask for a generous portion of grapes with margarine, Walfrido's favorite snack!
However, the room will only grant the wish if Thawan can solve the following problem:
Consider a regular polygon with $$$N$$$ vertices, numbered from $$$0$$$ to $$$N - 1$$$ in a clockwise direction. Thawan starts his journey at vertex $$$0$$$. In each move, he makes a jump of size $$$S$$$, advancing exactly $$$S$$$ vertices clockwise. That is, if he is currently at vertex $$$x$$$, the jump will take him to vertex $$$(x + S) \bmod N$$$.
Knowing that Thawan can continue jumping indefinitely, determine the maximum number of distinct vertices he will be able to visit along his path. Help Thawan secure Walfrido's snack!
The only input line contains two integers, $$$N$$$ and $$$S$$$ ($$$1 \le S \le N \le 10^9$$$), representing the number of vertices of the polygon and the size of Thawan's jump, respectively.
Print a single integer representing the number of distinct vertices Thawan can reach.
2 1
2
14 8
7
| Name |
|---|


