If I enter for example 150000 I get overflow , (y-1)x^5 passes limitation of any type.

Do I need to create new type to keep ((10^8)^5)size value ?
Or anything else I have to do with values, expression?

It may take around ten minutes if you precalc in Python.

It takes just few moments to precalc in C++.

Maybe special Python libraries for calculations would be OK.

There *is* a period of 9973, but not for the given function.

Let's denote 9973 as M.

//////////////////////////////////////////////////////////////////////////
//In short////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

1. g(n) is linear by f(n - 1), and g(x, y) = g(x mod M, y), which means we can find such A and B (in O(M)) that f(x + M) = (A * f(x) + B) mod M.

2. Having found such A and B, it's easy to show that for p > 0, f(p * M) = B * (A^(p-1) + A^(p-2) + .. + A^2 + A + 1) mod M.
I'm not sure if the last sum can be calculated in O(1), but it surely can be found in O(M).

3. So, we calc A and B, read N, find f(N - N % M) and then iterate till N in O(M), resulting with overall O(M).


//////////////////////////////////////////////////////////////////////////
//In detail///////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

//////
//1.//
//////

Let's assume we know f(i) and wish to find f(i+1).
Easy to see, g(x, y) = g(x mod M, y). This is why,

f(i + 1) = g(i + 1, f(i)) = g((i + 1) mod M, f(i)).

Let's denote (i + 1) mod M as j.

f(i + 1) = g(j, f(i)) =  ((f(i) - 1) * j^5 + j^3 – j * f(i) + 3 * j + 7 * f(i)) mod M

f(i + 1) = f(i) * (j^5 - j + 7) + (-j^5 + j^3 + 3 * j) mod M

f(i + 1) = f(i) * ((j^5 - j + 7) mod M) + (-j^5 + j^3 + 3 * j) mod M

Remembering that j = (i + 1) mod M, let us denote

U(i) = (j^5 - j + 7) mod M,
V(i) = (-j^5 + j^3 + 3 * j) mod M.

As a result:

f(i + 1) = U(i) * f(i) + V(i)

Note that for any i, we calculate U(i) and V(i) in O(1) time.
Also note that U(i) = U(i mod M) and V(i) = V(i mod M):

f(i + 1) = U(i mod M) * f(i) + V(i mod M)

Let's consider some certain x, and let's denote f(x) as X.

f(x+0) == X == 1 * X + 0 == (a0 * X + b0)    (mod M)
f(x+1) == U(0) * f(x+0) + V(0) == (a1 * X + b1)    (mod M)
f(x+2) == U(1) * f(x+1) + V(1) == (U(1) * a1) * X + (U(1) * b1 + V(1)) == (a2 * X + b2)    (mod M)
f(x+3) == U(2) * f(x+2) + V(2) == (U(2) * a2) * X + (U(2) * b2 + V(2)) == (a3 * X + b3)    (mod M)
f(x+4) == U(3) * f(x+3) + V(3) == (U(3) * a3) * X + (U(3) * b3 + V(3)) == (a4 * X + b4)    (mod M)
...
f(x+M) == (aM * X + bM))    (mod M)

Note that aM and bM do not depend on x - this is the key point!

Let's denote aM as A and bM as B. Each iteration above needs O(1) time, so we found A and B in O(M), such that for any x,

f(x+M) = (A * f(x) + B) mod M

//////
//2.//
//////

Consider the following sequence

f(0 * M) == 0    (mod M)
f(1 * M) == A * f(0 * M) + B == B    (mod M)
f(2 * M) == A * f(1 * M) + B == A * B + B == B * (A + 1)    (mod M)
f(3 * M) == A * f(2 * M) + B == A * B * (A + 1) + B == B * (A^2 + A + 1)    (mod M)
...
f(p * M) == B * (A^(p-1) + A^(p-2) + .. + 1)    (mod M)

Function A^p mod M is periodic by p with period being divisor of M, so we can easily calculate f(p * M) in O(M) time by summing up first M items of the sequence above.

Moreover, for this particular problem p (see below) is very small - less than N/M, so we may calculate this sum explicitly.

//////
//3.//
//////

The most pleasant part. Given N, we set p to N / M, and calculate f(p * M) with the method desribed above. N - p * M < M, so all we have to do left is explicitly apply the initial formula N - p * M times to find f(N).

Edited by author 15.02.2006 18:23

Can you please tell me is this array correct
{0,5392,1890,84,6520,3149,2416,2835,80,8614,742,7696,6823,
9492,7710,9444,510,118,6522,3213,4499,6178,4565,763,1071,
8875,2688,9145,1211,9480,4056,1817,8661,5467,3358,2892,
2205,8691,1963,2386,8401,1047,3691,6824,825,7728,6797,1720
8194,9901,2823,1952,9344,5022,1421,6116,4511,1289,2133,
7494,7298,5012,9638,8753,5968,4029,4804,9556,924,1497,5886
6078,2085,3876,268,2910,8962,2970,1015,3931,1103,4872,4054
346,1119,931,4454,6530,1722,4266,9888,7961,2891,885,4461,
7731,3316,2155,93,2871,9710}
q[i]=f(i*10^6),i from 0 to 100

Edited by author 18.12.2006 12:52

Edited by author 18.12.2006 12:53

easy, you just generate the solutions for 0..100 millions and then you just calculate 1 million values with that algorithme...

478704
478705
482574

Thanks.

47
475
4825

Thanks.

Edited by author 07.07.2006 15:07

g(x,y)=((y-1)*x^5+x^3+3*x-x*y+7*y) mod M
The result is in 0..M-1
But while counting it I have problems with type.
How to make it work with big values (For expample, If x=1000000)?

Thanks.

10000
20000
30000
40000
50000
60000
482574
958764057
2940376458

For these values:

46787954
23422479
3214893
16549853
24895423

Or give me a hint about testcase #14.