WC '01 P6 - Mission Impossible 3 - Olympiads Online Judge

WC '01 P6 - Mission Impossible 3

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 16M

Problem type

Woburn Challenge 2001

Well, as it turns out, James Bond successfully escaped the CBS attack helicopter and was debriefed at IMF headquarters in Langley, VA. Unfortunately, the only information he was able to retrieve was $3$ ~3~ numbers ( $R$ ~R~, $a$ ~a~, $b$ ~b~) that would allow an IMF team to hack into CBS computers to obtain the name of the last Survivor. CBS computers are encrypted using $1$ ~1~ numerical key that is not divisible by either $a$ ~a~ or $b$ ~b~ (note that if it was divisible, it would make cracking it substantially easier). It also turns out that $R$ ~R~ is the maximum number that they could have used for the encryption key.

With only this limited information, the only way to hack into the computer would be to determine the decryption key for each possible encryption key and try each of the decryption keys individually to see if they worked. Now keep in mind that all secure computers are placed in rooms with 50 ft ceilings and aerial access through ventilation ducts, and so the IMF insertion will undoubtedly involve Ethan Hunt hanging upside down from the roof of this room typing on the computer. A man can only hang upside down so long before blood pools in his brain causing loss of consciousness, so he can only try a limited number of decryption keys before he goes unconscious.

The question is this: how many decryption keys can we rule out? i.e. how many positive numbers $\le R$ ~\le R~ are divisible by either $a$ ~a~ or $b$ ~b~ (the more keys we can rule out, the fewer keys need to be tried)

Input Specification

The first line contains $T$ ~T~, the number of test cases.

Each of the remaining $T$ ~T~ lines is a test case consisting of the three positive integers $R$ ~R~, $a$ ~a~, $b$ ~b~ on a line.

Constraints

$1 \le T \le 100$ ~1 \le T \le 100~

Subtask 1 [50%]

$1 \le a, b \le 32\,767$ ~1 \le a, b \le 32\,767~

$\sum_{i=1}^T R_i \le 32\,767$ ~\sum_{i=1}^T R_i \le 32\,767~

Subtask 2 [50%]

$1 \le R, a, b \le 2\,000\,000\,000$ ~1 \le R, a, b \le 2\,000\,000\,000~

Output Specification

For each input, print the number of positive integers less than or equal to $R$ ~R~ that are divisible by $a$ ~a~ or $b$ ~b~.

Sample Input

Sample Output

16
15
6

Comments

0

maxcruickshanks commented on Oct. 17, 2021, 5:08 p.m. ← edited →

Since the original data were weak, $2$ ~2~ batches (each worth $50$ ~50~ marks) with $50$ ~50~ test cases were added to replace it.

2

Plasmatic commented on June 10, 2021, 1:47 a.m. ← edited →

$R, a, b \le 32\,767$ ~R, a, b \le 32\,767~

Bonus: $R, a, b \le 2\,000\,000\,000$ ~R, a, b \le 2\,000\,000\,000~

There are actually $2$ ~2~ cases in this problem (equally weighted), one where the constraints match $R, a, b \le 32\,767$ ~R, a, b \le 32\,767~ and another where they match the 'bonus' constraints.