GCJ 10 Round 3 Problem A De-RNG-ed

A problem looks simple but hard to get correct.

1. Observations: for k=1 and k=2, and whether S[0] == S[1]

2. Now the formula becomes clear,

S[0]*A + B = S[1] mod P
S[1]*A + B = S[2] mod P

A = (S[2]-S[1])*(S[1]-S[0])^-1 mod P
B = S[1] - S[0]*A

3. How to compute multiplicative inverse?
3.1 Method 1, extended Euclidean Algorithm. The easiest impl is to use recursion

pair gcd(int a, int p)
{
if (p%a==0) return make_pair(1,0);
pair pp = gcd(p%a,a);
int aa = pp.first; int bb = pp.second;
return make_pair(bb-aa*(p/a) , aa);
}

3.2 Method 2, use the fact that a^p = a mod p for prime p
inverse is then mypow(a,p-2)
int mypow(int a, int d, int p)
{
int ret = 1;
while(d)
{
if (d&1) ret = (ret*a)%p;
a = (a*a)%p;
}
return ret;
}

4. Watch integer overflow. Once it gets to 10^6, square it gets 10^12, which is more than MAX_INT.

5. When round a negative number to 0 to P-1, use a = a%p, if (a < 0) a+=p;
a while loop like while(a < 0) a += p; kills you, the running time goes up from a few seconds to 13 min.

6. Precompute primes using naive sieve.

7. Optional, may use binary search to find first prime to work on, but no significant saving in time. Makes no difference in this problem in terms of time.