Cheerio Contest 2 P4 - Modulus Finding

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

You are given four integers A, B, C, D that satisfy the equations A \bmod X = B and C \bmod X = D, where X is a positive integer. Output all possible values of X. It is possible that there are none — in which case you do not need to output anything.

Constraints

For all subtasks:

  • 1 \le A, B, C, D \le 10^{12}
  • B < A and D < C
Points Awarded Additional Constraints
3 points A = C and B = D
5 points 1 \le A, B, C, D \le 10^6
7 points No further constraints

Input Specification

The only line of input contains four integers A, B, C and D.

Output Specification

Output all possible values of X, each on their own line and in ascending order.

Sample Input

13 1 10 2

Sample Output

4

Explanation for Sample

13 \equiv 1 \pmod{4} and 10 \equiv 2 \pmod{4}. It can be shown that this is the only possible value of X.


Comments

There are no comments at the moment.