1994 ACM Student Programming Contest

Pacific Region

Problem E: Difference Sets

The difference set of an integer N is the set of all non-
negative integers P such that all of the following
conditions are true:

  - S and T are integers;
  - P = S - T;
  - N = S x T.
  
For example, the difference set of 35 is {34,2}, since
(1x35) and (7x5) are the only integer factor pairs of 35,
and (35-1)=34 and (7-5=2) are the only non-negative values P
which can be derived from these integer factor pairs
according to the above conditions.  As another example, 0 is
in the difference set of 625 and so is 120, since
625=(125x5) and (125-5)=120, and 625=(25x25) and (25-25)=0.

Write a program that will determine whether a given integer
P is in the difference set of another given integer N.  The
input to your program will be a file containing a series of
lines.  Each line will contain two integers, N and then P.
N starts in column 1, and is followed by one or more blanks,
then P.  Each line is terminated with an end of line.  The
size of the integers N and P may be up to 20 digits each.

The output of your program is to contain one line for each
input data line.  If the input integer P is not in the
difference set of the input integer N, the output should
give both the input values and indicate that P is not in the
difference set of N.  If the input integer P is in the
difference set of N, the output should give the original
input value P and the factors S and T of N which when
subtracted yield the value P.  You should leave at least one
blank line between consecutive output data lines.

For example, given the input file

123456789876543 3571
100011100011 899990

the corresponding output would be:

3571 is not in the difference set of 123456789876543

899990 = 1000001 - 100011