Divisibility Rules

It is often useful in mathematics to decide whether one integer is divisible by another. For example, if you multiply an integer by 7 (without using a calculator!) you may want to check quickly that you have performed the multiplication correctly by ensuring that the product is divisible by 7 (this does not guarantee that you were correct, but if it fails, you can be certain that your answer was incorrect.)

Most probably, you learned the rules for divisibility by 2, 3, 4, 5, 6, 9, and 10 in elementary school, and possibly 8 — but not 7! Most elementary school teachers will admit to not knowing the divisibility rule for 7, which is as follows:

  1. If the number has 1 or 2 digits, stop.
  2. Remove the last digit from the number and double it.
  3. Subtract the result from the rest of the number.
  4. Go back to step 1.

For example, let's say we want to check whether or not 13076 is divisible by 7. We remove the 6, double it to get 12, and then subtract 12 from 1307 to obtain 1295. We then remove the 5, double it to get 10, and subtract 10 from 129 to get 119. We then remove the 9, double it to give 18, and subtract 18 from 11 to obtain -7. Since this is divisible by 7, we can conclude that 13076 is divisible by 7.

Enter the proverbial PEG member who is brilliant at programming but lousy at short questions. He (she?) is doing some Computer Number Systems homework. However, using the computer to answer the question of whether or not x is divisible by y, is akin to using a calculator, and is therefore not allowed. Instead, he decides to write a program that will find a divisibility rule, given a divisor and a base, so that he can carry out the check by hand. After he finishes this unbelievably easy task, he bets you points in Ms. Plachta's computer science class that you can't solve this problem... but can you?

Task
Given a base and a divisor, find a rule of the form "repeatedly remove the last digit, multiply it by X, and then add it to (or subtract it from) the rest of the number" that can be used to check the divisibility of a number written in the given base by a given divisor. Yes, we know that there are often much better divisibility rules. (For example, to test for divisibility by 37 in base 10, you break the number into chunks of three digits each, starting from the right, and add up all of the chunks.) However, our proverbial PEG member is the "brilliant but lazy" type and he didn't go as far as to check for such rules.

Input
The first line of the input contains an integer T (1 ≤ T ≤ 100). The next T lines contain two integers B (1 < B ≤ 100) and K (1 < K ≤ 100). B and K have no common divisor other than 1, and are expressed in base 10.

Output
For each test case, output a line containing either + or - followed by an integer X (with no space separating the two). The output "+X" signifies that one is to remove the last digit, multiply it by X, and add it to the rest of the number, whereas "-X" signifies that one is to remove the last digit, multiply it by X, and subtract it from the rest of the number. If there are multiple solutions, output the one with the smallest value of X. If there is still a tie, output +X in preference to -X. X should be expressed in base 10.

Sample Input
2
10 7
6 5

Sample Output
-2
+1

Explanation
In the first test case, we are asked to find a base 10 divisibility rule by 7. The answer, as already stated, is to remove the last digit, double it, and subtract this from the rest of the number. In the second test case, we are asked to find a base 6 divisibility rule by 5. The solution is to remove the last digit and add it to the rest of the number, hence 123456 is divisible by 5: 1234 + 5 = 1243; 124 + 3 = 131; 13+1 = 14; 1+4 = 5.

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 19, 2008
Author: bbi5291

Problem Types: [Show]

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

Comments (Search)

bbi5291 on Nov 29, 2008 - 5:35:28 pm UTC Hint
  • (2/0)
The mathematical justification of the solution is long and complicated, but... first solve the problem in base 10. Notice that 20+1 is a multiple of 7. Here's another rule: to check for divisibility by 13 in base 10, you quadruple the last digit and add it to the rest of the number. Notice here that 40-1 is a multiple of 13.