|
|
back to boardShow all messages Hide all messagesyou 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... 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.
|
|
|
