Woburn Challenge 2001

6) Mission Impossible 3

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 numbers (R, a, 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 numerical key that is not divisible by either a or b (note that if it was divisible, it would make cracking it substantially easier). It also turns out that 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 ≤ R are divisible by either a or b (the more keys we can rule out, the fewer keys need to be tried)

Input

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

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

Assumptions

R, a, b ≤ 32,767

Bonus: R, a, b ≤ 2,000,000,000

Output

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

Sample Input

3
50 3 21
63 6 8
34 8 15

Sample Output

16
15
6

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 23, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

So, the second test case is too large for Pascal longint...?

Actually, longint goes up to 2147483647, so it is big enough.

nvm I just did it with real , and it worked

Thanks anyways! :)

it should be the part where i find the number of numbers that are divisible by both a and b, but i can't find my error.

Your formula is wrong. (Does it even work for the sample input?)
Also, you should give your variables meaningful names - your code is very hard to understand.

whoops - my bad - stupid question.

Just for checking the problem out, I tried doing a for loop that will increase 'x' by one everytime a number between 1 to 50 satisfies num %% 3 or 21...

it gave me 18.

I tried putting in the second sample and it gave me 17 while the third one gave me 6...

because there are numbers which are multiples of both 3 and 21, such as 21 and 42.

Instead of using a loop, try to think of a mathematical way of determining how many multiples of a number are within the interval 1 to R, where R is the first number in the input.  Do this for the second number, as well and then you have to ensure that you only count numbers once (i.e. you don't count 21 and 42 twice like in your case).

Oh, and I believe having a for loop that goes up to 2,000,000,000 will time out.

ohh..Thanks!!

OK I tried that but it still doesn't work...Don't get it.

ok then.

1) find the number of multiples of a in the inputted range.
2) find the number of multiples of b in the inputted range.
3) find the overlap.
4) subtract.

edit:  sorry, admins, If I said too much.  edit this as you see fit.

A second case with R <= 2,000,000,000 has been added.
(Don't worry, partial marks are enabled)