Internet Problem Solving Contest

IPSC 2009

Solution to Problem D – Don't worry about wrong answers


There were two valid strategies. The simplest one was just to submit something clearly wrong as soon as you read the problem.

The second strategy, obviously, involves solving the problem to find the inputs that cause WRONG ANSWERs, and submit these for a time bonus.

For the second strategy, you have to make an educated guess whether to do it or not. More precisely, you should estimate how long it will take you to solve the task. Note that if you spend T minutes solving this task, then each of the tasks you solve afterwards will be submitted T minutes later, thereby accumulating your time penalty. Thus you should only attempt this strategy if you are fast.

Easy data set

Function foo is better known as Euclid’s algorithm calculating the greatest common divisor and function bar is a very clumsy way of testing primality of a given number: if p is a prime number then it doesn’t have a common divisor greater than one with any number q < p – gcd(p,q) = 1 for every 1 q < p. On the other hand, if n = d k, than gcd(n,d) = d and gcd(n,k) = k, so the converse holds too.

Thus we get a WRONG answer only if we find a prime number n in the given interval 100000000–198765432 such that numbers n + 18, n + 36, etc. are also primes. These numbers couldn’t be found using the given program (in a reasonable time). It is way to slow even for testing a single number. A good way to solve this problem was to use the sieve of Eratosthenes and then sweep through the array and find the primes satisfying the given funny condition.

There are 14 such numbers: 186613711, 126605623, 143819771, 118810171, 123372071, 128293463, 196192091, 194990891, 172496083, 175066651, 132058483, 106961383, 117340703 and 142425763.

Hard data set

The hard problem was to find all the square roots of 1 (mod N). We call x a square root of a, if a is a square of x i.e., x2 = a (equivalently, a square root of a is a root of the quadratic equation x2 - a = 0).

The square roots may be different depending on what numbers we work with, for example:

In particular, note that there are two square roots of 1 – this is always true, if we work with integers modulo p, where p is any prime number (except 2). This is because x2 - 1 = (x- 1)(x + 1) and this is 0 (mod p) if and only if p divides (x - 1)(x + 1), which is if and only if p divides x - 1 or p divides x + 1. If 0 < x < p, then either x = 1 or x = p- 1. Note that p- 1 is the same as -1 (mod p) and it is easy to see that (-1)2 = (+1)2 = 1 (mod p). To sum up:

Fact 1: There are exactly two square roots of 1 (mod p) where p is a prime number, p > 2, namely 1 and p - 1.

The last example may be obviously generalized to a simple fact:

Fact 2: If we work with n-tuples (a1,a2,,an), with multiplication defined as multiplying the corresponding elements independently) and there are exactly ri square roots of 1 for the i-th element, then there are exactly r1 r2⋅⋅⋅rn square roots of (1,1,,1).

Now how can we find the square roots mod 15? A “low level” approach: 15 = 3 5, so if 15 divides x2 - 1 = (x - 1)(x + 1), then either 15 divides (x - 1) (so x = 1), or 15 divides x + 1 (so x = 14), or 3 divides x - 1 and 5 divides x + 1 or 5 divides x - 1 and 3 divides x + 1. Take the last case: x - 1 = 5k and x + 1 = 3(for some k,ℓ), so x = 5k + 1 = 3- 1 and 3- 5k = 2. Numbers k and can be found using extended Euclidean algorithm (see http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm, http://en.wikipedia.org/wiki/Bzout’s_identity).

A more “high level” view: There is a one-to-one correspondence between numbers mod 15 and pairs (a,b), where a is mod 3 and b is mod 5; specifically, number n corresponds to pair (n mod 3,n mod 5). Furthermore, multiplying two numbers mod 15 corresponds to multiplying the corresponding pairs; in particular, square roots of 1 mod 15 correspond to square roots of (1,1) mod 3,5. We already know the square roots of (1,1) are (+1,+1), (+1,-1), (-1,+1) and (-1,-1). Thus all square roots of 1 mod 15 are numbers x such that

x ≡ ±1  (mod 3)    x ≡ ±1  (mod  5).
The solutions can be found by Chinese remainder theorem.
See http://en.wikipedia.org/wiki/Chinese_remainder_theorem.

Chinese remainder theorem: Given pairwise coprime integers n1,,nk and any integers a1,,ak, the system of simultaneous congruences

x ≡ a   (mod  n )   ⋅⋅⋅    x ≡ a  (mod n )
     1        1               k        k
has one unique solution mod N = n1 n2⋅⋅⋅nk.

To solve the hard problem you should factorize number N first.

N  =   655076673443707551099143071618051666714277042558983269995765119

   =   1157710228741282062487⋅943753934567180439929⋅599561157376811721953
This is quite a big number with big prime factors, so the naïve factorization algorithms would take centuries to fulfill this task. However using e.g. http://www.alpertron.com.ar/ECM.HTM, the number can be factorized in few seconds.

Since N = pqr is a product of 3 prime numbers, there are exactly 8 square roots mod N corresponding to tripples (±1 mod p,±1 mod q,±1 mod r). To find them we used the following program:

p = 1157710228741282062487; q = 943753934567180439929; r = 599561157376811721953  
m = [p, q, r]  
def extgcd(a, b):  
  if b == 0: return (a, 1, 0)  
  d, u, v = extgcd (b, a  
  return (d, v, u-(a/b)*v)  
def crt(y, m):  
  x = y[0]; M = M2 = m[0]  
  for i in xrange(1,len(m)):  
    d,u,v = extgcd (M, m[i])  
    M2 *= m[i]  
    x += (M*u  
    M = M2  
  return x  
print crt ([p-1,q-1,r-1], m)  
print crt ([  1,q-1,r-1], m)  
print crt ([p-1,  1,r-1], m)  
print crt ([p-1,q-1,  1], m)  
print crt ([p-1,  1,  1], m)  
print crt ([  1,q-1,  1], m)  
print crt ([  1,  1,r-1], m)

Excluding the trivial square root 1 (which gave correct answer), these 7 numbers gave the WRONG ANSWER:
(The first number, N - 1 ≡-1 mod N, could be found without much effort.)