# Internet Problem Solving Contest

## IPSC 2009

Strategy

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:

• if we work with positive real numbers, there is only one square root of 3 (but there is no square root of 3 e.g. in rational numbers)
• if we work with all real numbers, there are two square roots of 3 (both and - satisfy the definition above), but there is no square root of -1 (however, there are two square roots of -1 in complex numbers: i and -i)
• if we work with integers, there are two square roots of 4 (but no square root of 5 or -4)
• if we work with integers modulo 7, then 02 = 0, 12 = 1, 22 = 4, 32 = 9 2, 42 = 16 2, 52 = 25 4 and 62 = 36 1; so 1, 4 and 2 have exactly two square roots (mod 7) and 3, 5 and 6 don’t have a square root (mod 7);

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.

• if we work with integers modulo n, where n is not prime, then 1 and n - 1 ≡ -1 (mod n) are surely square roots of 1, however, there are more; for example take integers modulo 15, then 12 = 1, 142 (-1)2 = 1, but also 42 = 16 1 and 112 = 121 1 (mod 15) – note that actually 11 = -4 (mod 15), so we should have already known that 112 (-4)2 = 42 1.
• finally, lets take pairs of integers (a,b) modulo 7; lets multiply these pairs this way: (a,b) (c,d) = (ac mod 7,bd mod 7), so in particular, (a,b)2 = (a2 mod 7,b2 mod 7); what are the square roots of (1,1)? well, we already know that there are two square roots of 1 modulo 7, namely ±1 so there are exactly 4 square roots of (1,1), namely: (+1,+1), (+1,-1), (-1,+1) and (-1,-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 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 has one unique solution mod N = n1 n2 nk.

To solve the hard problem you should factorize number N first. 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; M = M2 = m    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:
655076673443707551099143071618051666714277042558983269995765118,
423708042681157396922466745853617748770106296874520998638487956,
409195345538471765371894681196161478839399343815134048305305493,
477249958667785939903924716186324105819048444428311493047736788,
231368630762550154176676325764433917944170745684462271357277163,
245881327905235785727248390421890187874877698743849221690459626,
177826714775921611195218355431727560895228598130671776948028331.
(The first number, N - 1 ≡-1 mod N, could be found without much effort.)