Mock CCC '19 Contest 2 J5 - Tudor Drinks Even More Tea

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.75s
Java 1.4s
PyPy 2 2.5s
PyPy 3 2.5s
Memory limit: 1G

Problem type

Tudor hasn't had enough tea yet?

Tudor has prepared two cups of tea this time, each one with a certain number of micrograms of sugar. Tudor is superstitious and does not like it when the counts of micrograms of sugar are not relatively prime. The cups of tea must have integer micrograms of sugar.

Recall that two integers are relatively prime if their greatest common divisor is 1.

Given that the first cup of tea must have between A and B micrograms of sugar and the second cup of tea must have between C and D micrograms of sugar, compute the number of distinct ways Tudor can prepare the cups of tea.


1 \le A \le B \le 10^7

1 \le C \le D \le 10^7

In tests worth 5 marks, B \le 10^2 and D \le 10^2.

Input Specification

The input will consist of a single line containing four space-separated integers, A, B, C, and D.

Output Specification

Output, on a single line, the number of distinct valid configurations of tea.

Sample Input

1 2 1 2

Sample Output


Sample Explanation

There are four possible ways to insert sugar, the only one of which is invalid when Tudor adds 2 micrograms of sugar to both.


There are no comments at the moment.