Hate Coprime
Time limit1sMemory limit1024 MB
Given x and y, add or subtract a z that shares a factor with the current x, at most twice, so that x becomes equal to y.
- Level
Medium6 of 10
- Topics
- Number theory, Math, Implementation
- Solved
- No attempts yet
Problem
Two integers and are given, with . Using the following operation at most twice, make and equal.
- Choose an integer with that is not coprime to . Add to , or subtract from .
After each operation, must still be an integer with .
It can be proven that can always be turned into with at most two operations.
Output
The first line contains the integer , the number of operations used .
From the second line onward, print the operations in order, one per line.
- If the operation adds to , print .
- If the operation subtracts from , print .