| ENG RUS | Timus Online Judge |
Discussion of Problem 1309. Disputetbtbtb How to slove it fast.......... [12] // Problem 1309. Dispute 27 Apr 2004 15:00 Gheorghe Stefan Re: How to slove it fast.......... [11] // Problem 1309. Dispute 4 May 2004 16:15 you can generate all result with a rate of Zhang Jin Jing But I think it very large and seems no disciplinarians [10] // Problem 1309. Dispute 5 May 2004 14:41 Gheorghe Stefan Re: But I think it very large and seems no disciplinarians [9] // Problem 1309. Dispute 7 May 2004 14:55 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. hello Re: But I think it very large and seems no disciplinarians [8] // Problem 1309. Dispute 30 May 2004 19:41 I'm puzzled. I don't understand your way. How to get 2 millions values from 1 million ? Vlad Veselov Re: But I think it very large and seems no disciplinarians [7] // Problem 1309. Dispute 31 May 2004 17:18 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). hello Re: But I think it very large and seems no disciplinarians [6] // Problem 1309. Dispute 31 May 2004 23:03 Oh. Thank you very much !!! But I don't think it is a very good way . Do you know the better way ? Vlad Veselov No one knows the better way [5] // Problem 1309. Dispute 1 Jun 2004 16:30 hello Re: No one knows the better way [4] // Problem 1309. Dispute 1 Jun 2004 20:04 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 Gheorghe Stefan No subject [3] // Problem 1309. Dispute 3 Jun 2004 19:26 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... Pasha Re: No subject [2] // Problem 1309. Dispute 22 Jul 2004 16:15 Gheorghe Stefan wrote 3 June 2004 19:26 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! Gheorghe Stefan Re: No subject [1] // Problem 1309. Dispute 23 Jul 2004 01:03 so I was mistaken, it was only 100 mil... so what? big deal... N.M.Hieu ( DHSP ) I have a best way to do it ! // Problem 1309. Dispute 11 Jul 2005 22:04 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. |