Google Code Jam '10 Round 1A Problem C - Number Game

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 90.0s
Memory limit: 1G

Problem types

Arya and Bran are playing a game. Initially, two positive integers A and B are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace A with A - k \cdot B for any positive integer k, or replace B with B - k \cdot A for any positive integer k. The first person to make one of the numbers drop to zero or below loses.

For example, if the numbers are initially (12, 51), the game might progress as follows:

  • Arya replaces 51 with 51 - 3*12 = 15, leaving (12, 15) on the blackboard.
  • Bran replaces 15 with 15 - 1*12 = 3, leaving (12, 3) on the blackboard.
  • Arya replaces 12 with 12 - 3*3 = 3, leaving (3, 3) on the blackboard.
  • Bran replaces one 3 with 3 - 1*3 = 0, and loses.

We will say (A, B) is a winning position if Arya can always win a game that starts with (A, B) on the blackboard, no matter what Bran does.

Given four integers A_{1}, A_{2}, B_{1}, B_{2}, count how many winning positions (A, B) there are with A_{1} \le A \le A_{2} and B_{1} \le B \le B_{2}.

Input Specification

The first line of the input gives the number of test cases, T. T test cases follow, one per line. Each line contains the four integers A_{1}, A_{2}, B_{1}, B_{2}, separated by spaces.

Output Specification

For each test case, output one line containing Case #x: y, where x is the case number (starting from 1), and y is the number of winning positions (A, B) with A_{1} \le A \le A_{2} and B_{1} \le B \le B_{2}.

Limits

Memory limit: 1 GB.

1 \le T \le 100.

1 \le A_{1} \le A_{2} \le 1\,000\,000.

1 \le B_{1} \le B_{2} \le 1\,000\,000.

Small Dataset

Time limit: 30 seconds.

A_{2} - A_{1} \le 30.

B_{2} - B_{1} \le 30.

Large Dataset

Time limit: 90 seconds.

A_{2} - A_{1} \le 999\,999.

B_{2} - B_{1} \le 999\,999.

No additional constraints.

Sample Input

3
5 5 8 8
11 11 2 2
1 6 1 6

Sample Output

Case #1: 0
Case #2: 1
Case #3: 20

Note

This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >90.000s regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.


Comments

There are no comments at the moment.