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

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.5s
Java 3.0s
PyPy 2 5.0s
PyPy 3 5.0s
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.

Constraints

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

3

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.


Comments

There are no comments at the moment.