| ENG RUS | Timus Online Judge |
Discussion of Problem 1343. Fairy TaleFat Peter I got TLE on test9.who can tell me how to solve it? [17] // Problem 1343. Fairy Tale 23 Feb 2005 07:47 Dmitry 'Diman_YES' Kovalioff. Retired Something that might help you (+) [13] // Problem 1343. Fairy Tale 23 Feb 2005 10:37 I doubt there is another way to solve this problem, but to check random suffixes until the prime number is found. As for me, I just used precalc feature to find all the prime numbers less than 1000000, and then tested numbers using this list. My solution gets AC within 0.48 sec. How to check whether the number is prime or not faster? I don't think it is possible here. Miller-Rabin heuristics will obviously fail, because Int64 is not enough to store 24-digit number while modular exponentation. It might be passed, of course, but for what? :) Anyway, some tests for you: 0 923802054017 // 1 1 192380205401 // 12 192380205401 192380205401 // 11 92380205401 923802054017 // 11 00000000000 000000000005 - be careful, I doubt 000000000000 and 000000000001 are ok! // 10 0123456789 012345678923 Vladimir Yakovlev (USU) Re: Something that might help you (+) // Problem 1343. Fairy Tale 23 Feb 2005 15:14 I also generated random suffixes, but check them straightforward in O(sqrt(N)), and gets AC in 0.031. See http://acm.timus.ru/status.aspx?space=1&pos=745502 Fat Peter Re: Something that might help you (+) // Problem 1343. Fairy Tale 26 Feb 2005 09:21 My program will get TLE when L=12,but I suppose that my programs was to slow leads to TLE. Thank you very much. Yuanming YU, Frank Miller-Rabin heuristics will obviously fail? I don't think so! [8] // Problem 1343. Fairy Tale 3 Mar 2005 19:05 I used Miller-Rabin heuristics got AC...... You say Int64 is not enough to store 24-digit number Why you have to store 24-digit? In my pro,I think 19-digit is enough... There is a trick to avoid this situation......so one "mod" still take O(1) time...... If you are good at maths,it is not very hard to think out Good luck! Vladimir Yakovlev (USU) Re: Miller-Rabin heuristics will obviously fail? I don't think so! [7] // Problem 1343. Fairy Tale 4 Mar 2005 01:20 Yuanming YU, Frank wrote 3 March 2005 19:05 There is a trick to avoid this situation......so one "mod" still take O(1) time...... I know how to mutiply integers up to 2^63 in O(log N) time: // multiply a and b modulo c typedef unsigned __int64 ull; ull Mul(ull a, ull b, ull c) { if (b == 0) return 0; if (b == 1) return a%c; ull d = Mul(a, b/2, c); d = (d+d)%c; if (b%2 == 1) d = (d+a)%c; return d; } But how to do it in O(1) time? Yuanming YU, Frank Re: Miller-Rabin heuristics will obviously fail? I don't think so! [6] // Problem 1343. Fairy Tale 4 Mar 2005 10:58 Sorry,I didn't say it clearly...... calc a^n mod b certainly take at least O(logn) time... I meant that calc a*a mod b in O(1) time,although a may as large as 10^13-1,a*a>int64 ... so Miller-Rabin heuristics still work......just like in small cases...... Vladimir Yakovlev (USU) Can you tell how to do it? [5] // Problem 1343. Fairy Tale 4 Mar 2005 22:32 Yuanming YU, Frank your email [4] // Problem 1343. Fairy Tale 5 Mar 2005 10:34 Dmitry 'Diman_YES' Kovalioff. Retired Enlighten me too, please :) - dimanyes@yahoo.com (-) [1] // Problem 1343. Fairy Tale 5 Mar 2005 11:47 ronobe (aka oberon) And me, please... // Problem 1343. Fairy Tale 5 Mar 2005 20:24 oberon @ verba.com.ua Vladimir Yakovlev (USU) See e-mail in my profile [1] // Problem 1343. Fairy Tale 5 Mar 2005 13:26 Yuanming YU, Frank Sent....check your email // Problem 1343. Fairy Tale 5 Mar 2005 20:14 Oleg Strekalovsky [Retired] Re: Something that might help you (+) [1] // Problem 1343. Fairy Tale 16 Jul 2010 00:21 Dmitry 'Diman_YES' Kovalioff. Retired wrote 23 February 2005 10:37 11 As I understand, 000000000000 is not right answer, but 000000000001 is right.00000000000 000000000005 - be careful, I doubt 000000000000 and 000000000001 are ok! Edited by author 16.07.2010 00:22 balandini Re: Something that might help you (+) // Problem 1343. Fairy Tale 13 Jun 2012 15:57 Edited by author 13.06.2012 16:36 Yuanming YU, Frank I use random algo // Problem 1343. Fairy Tale 3 Mar 2005 18:45 the expect running time of my algo is O(100*lognlogn)... judge whether a prime for 100 times... In practise, it did run very fast,AC in 0.031sec... morbidel Re: I got TLE on test9.who can tell me how to solve it? [1] // Problem 1343. Fairy Tale 7 Mar 2005 15:36 I used a simple idea: read N, put zeroes to fill up to 12 digits and then increase these new digits until N is prime... worked with __int64 from Visual C++ Smilodon_am [Obninsk INPE] Re: I got TLE on test9.who can tell me how to solve it? // Problem 1343. Fairy Tale 15 May 2010 13:25 Excellent idea. I have used it and got AC. Another good test: 11 00000000001 Ans: 000000000011 Edited by author 15.05.2010 13:26 |