Обсуждение @ 1343. 12 месяцев @ Timus Online Judge

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

Послано Fat Peter 23 фев 2005 07:47

Something that might help you (+)

Послано Dmitry 'Diman_YES' Kovalioff 23 фев 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 (+)

Послано Vladimir Yakovlev (USU) 23 фев 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 (+)

Послано Fat Peter 26 фев 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

Послано Neumann 3 мар 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!

Послано Neumann 3 мар 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!

Послано Vladimir Yakovlev (USU) 4 мар 2005 01:20

Neumann писал(a) 3 марта 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!

Послано Neumann 4 мар 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?

Послано Vladimir Yakovlev (USU) 4 мар 2005 22:32

your email

Послано Neumann 5 мар 2005 10:34

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

Послано Dmitry 'Diman_YES' Kovalioff 5 мар 2005 11:47

See e-mail in my profile

Послано Vladimir Yakovlev (USU) 5 мар 2005 13:26

Sent....check your email

Послано Neumann 5 мар 2005 20:14

And me, please...

Послано ronobe (aka oberon) 5 мар 2005 20:24

oberon @ verba.com.ua

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

Послано Gheorghe Stefan 7 мар 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?

Послано Smilodon_am 15 май 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 (+)

Послано Oleg Strekalovsky [Vologda SPU] 16 июл 2010 00:21

Dmitry 'Diman_YES' Kovalioff писал(a) 23 февраля 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 (+)

Послано balandini 13 июн 2012 15:57

Edited by author 13.06.2012 16:36

Обсуждение задачи 1343. 12 месяцев