you can generate all result with a rate of

you generate all values for 1 million, 2 millions and so on. You have only 1000 values. Then you only sweep the interval from previous checkpoint to N.

I'm puzzled.
I don't understand your way.
How to get 2 millions values from 1 million ?

You write a stupid program, which calculates values for all n and writes to file values for n = k * 10^6, where k is positive integer. Then you wait few minutes (hours,days...), while your program generates result. You make array of constants, where i-th value is f(n) for n = i * 10^6. When your program gets the value of n it finds k such that k * 10^6 <= n and (k + 1) * 10^6 > n and calculates values f(k*10^6+1),...,f(n).

Oh. Thank you very much !!!
But I don't think it is a very good way .
Do you know the better way ?

Oh. Thank you very much !!!
Your way is good .
I got AC just use 0.062s.
But I spend much time on making the answer of 1 , 2 , 3... millions.

Edited by author 01.06.2004 20:04

you can generate a value in O(N) time so for 1 billion, the maximum value, the program must run few seconds... mine worked in 10-15...

Why must you calculate this for 1 billion? In the problem clearely said: n from 0 to 100,000,000!
Thanks to Vlad Veselov! I've got AC!

so I was mistaken, it was only 100 mil... so what?
big deal...

It belongs my friend ! He came from China ! His solution is O(10000) in the worst case ! I haven't understood him yet ! So I will write there to everybody ! If someone understand , please explain for me !

Here the solution :

Suppose f(1)=a1*f(0)+b1 (mod 9973), then f(9973*i+1)==a1*f(9973*i)+b1 (mod 9973).

So after calculating the (a,b) in f(9973)=a*f(0)+b (mod 9973), then f(9973*(i+1))=a*f(9973)+b (mod 9973)

So we can get the algorithm with O(10000) in time.