Discussion @ 1343. Fairy Tale @ Timus Online Judge

I got TLE on test9.who can tell me how to solve it?

Posted by Fat Peter 23 Feb 2005 07:47

Something that might help you (+)

Posted by Dmitry 'Diman_YES' Kovalioff 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

Re: Something that might help you (+)

Posted by Vladimir Yakovlev (USU) 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

Re: Something that might help you (+)

Posted by Fat Peter 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.

I use random algo

Posted by Neumann 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...

Miller-Rabin heuristics will obviously fail? I don't think so!

Posted by Neumann 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!

Re: Miller-Rabin heuristics will obviously fail? I don't think so!

Posted by Vladimir Yakovlev (USU) 4 Mar 2005 01:20

Neumann 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?

Re: Miller-Rabin heuristics will obviously fail? I don't think so!

Posted by Neumann 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......

Can you tell how to do it?

Posted by Vladimir Yakovlev (USU) 4 Mar 2005 22:32

your email

Posted by Neumann 5 Mar 2005 10:34

Enlighten me too, please :) - dimanyes@yahoo.com (-)

Posted by Dmitry 'Diman_YES' Kovalioff 5 Mar 2005 11:47

See e-mail in my profile

Posted by Vladimir Yakovlev (USU) 5 Mar 2005 13:26

Sent....check your email

Posted by Neumann 5 Mar 2005 20:14

And me, please...

Posted by ronobe (aka oberon) 5 Mar 2005 20:24

oberon @ verba.com.ua

Re: I got TLE on test9.who can tell me how to solve it?

Posted by Gheorghe Stefan 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++

Re: I got TLE on test9.who can tell me how to solve it?

Posted by Smilodon_am 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

Re: Something that might help you (+)

Posted by Oleg Strekalovsky [Vologda SPU] 16 Jul 2010 00:21

Dmitry 'Diman_YES' Kovalioff wrote 23 February 2005 10:37

11
00000000000

000000000005 - be careful, I doubt 000000000000 and 000000000001 are ok!

As I understand, 000000000000 is not right answer, but 000000000001 is right.

Edited by author 16.07.2010 00:22

Re: Something that might help you (+)

Posted by balandini 13 Jun 2012 15:57

Edited by author 13.06.2012 16:36

Discussion of Problem 1343. Fairy Tale