### 1997 Canadian Computing Competition, Stage 1

# Problem E: Long Division

In days of yore (circa 1965), mechanical calculators performed division by shifting and repeated subtraction. For example, to divide 987654321 by 3456789, the numbers would first be aligned by their leftmost digit (see Figure 1 below), and the divisor subtracted from the dividend as many times as possible without yielding a negative number. The number of successful subtractions (in this example, 2) is the first digit of the quotient. The divisor, shifted to the right (see Figure 2 below), is subtracted from the remainder several times to yield the next digit, and so on until the remainder is smaller than the divisor.

Figure 1:987654321 - 3456789 first successful subtraction ======== 641975421 - 3456789 second successful subtraction ======== 296296521 remainder - 3456789 unsuccessful subtraction ======== negativeFigure 2:

296296521 - 3456789 ======== 261728631 etc.

Write a program to implement this method of division. See the input and output specifications below.

### Input

The first line of the input file contains a positive integer `n`, `n` < 20,
which represents the number of test cases which follow. Each test case is
provided on a pair of lines, with the number on the first line being the
dividend, and the number on the second line being the divisor. Each line will
contain a positive integer of up to 80 digits in length.

### Output

For each pair of input lines, your output file should contain a pair of lines representing the quotient followed by the remainder. Output for different test cases should be separated by a single blank line. Your output should omit unnecessary leading zeros.

### Sample Input

3 987654321 3456789 33 11 11 33

### Sample Output

285 2469456 3 0 0 11

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Sep 29, 2008

**Problem Types:**[Show]

**Languages Allowed:**

C++03, PAS, C, ASM, C#, C++11

## Comments (Search)

zhxl0903on Apr 17, 2010 - 7:50:05 pm UTC Can someone please explain to me how the subtraction in Figure 2 works?zhxl0903on Apr 17, 2010 - 10:23:36 pm UTC Re: Can someone please explain to me how the subtraction in Figure 2 works?bbi5291on Apr 18, 2010 - 8:12:07 pm UTC Re: Can someone please explain to me how the subtraction in Figure 2 works?ragulan5on Mar 15, 2009 - 7:12:43 pm UTC TLEultblad1on Mar 16, 2009 - 1:09:00 am UTC Re: TLEbbi5291on Mar 16, 2009 - 1:37:02 am UTC Re: Re: TLEragulan5on Mar 16, 2009 - 2:37:49 am UTC Re: Re: TLEseyonvon Oct 31, 2008 - 11:48:10 pm UTC what is alloweddo you have to use the method that it says to use

02fentymon Oct 31, 2008 - 11:53:52 pm UTCbbi5291on Nov 01, 2008 - 1:45:03 am UTC Can you keep a secret?there is no automated checking of source, so you are free to use whatever method you want for generating the output. Of course, short of simply hard-coding the output file (which would get you in trouble for sure), the method they gave you is undoubtedly the easiest to implement. The numbers given may be too large to fit in int/long long, so you can't use / and mod to solve this problem.