Discussion @ 1268. Little Chu @ Timus Online Judge

A easy problem

Posted by liuchang 10 Jun 2004 21:30

You may run it on your own computer.
Then you'll get the all answers.
Then......Got AC!!!

I ran the program for 2.5 hours in all!!!

Re: A easy problem

Posted by Pasha 12 Jul 2004 15:20

Yes, it was interesting to find all simple numbers in range 3 .. 65521 (There is only 6541 simple number in this range!) and calculate answer for each of them using SMART brute-force. It had taken only 17 minutes! And AC program weights about 91501 bytes!

A mathematical solution based on modular arithmetics gets AC within 0.25 s. (-)

Posted by Dmitry 'Diman_YES' Kovalioff 12 Jul 2004 21:30

Re: A mathematical solution based on modular arithmetics gets AC within 0.25 s. (-)

Posted by Saturn 13 Jul 2004 15:04

How to solve this problem by maths?

It is difficult to explain... (+)

Posted by Dmitry 'Diman_YES' Kovalioff 13 Jul 2004 19:36

Read "Introduction to Algorithms", chapter 33 - modular arithmetics, group generators, Lagrange theorem, etc.

Re: A easy problem

Posted by Future 5 Oct 2004 13:32

17 minutes? What kind of so called "smart brute-force"?
You can send to fujieyun@163.com to tell me your way.
Thanks.

Whole 17 minutes? My program takes about 30 seconds :-) (-)

Posted by Kit (Vologda SPU) 9 Sep 2005 00:19

Edited by author 09.09.2005 00:20

Re: Whole 17 minutes? My program takes about 30 seconds :-) (-)

Posted by Someone 19 Mar 2006 03:51

How did you reach this time?

Re: Whole 17 minutes? My program takes about 30 seconds :-) (-)

Posted by Someone 19 Mar 2006 15:54

Ok. I submited it. My worked 27 sec.

you only now got AC.

Posted by ACM.Tolstobrov_Anatoliy[Ivanovo SPU] 19 Mar 2006 17:17

Vladimir Yakovlev(USU)
91501 bytes > 64000 bytes

Where rejudge?

P.S. I too got AC with cheating [ 38kb ].

Re: you only now got AC.

Posted by Someone 19 Mar 2006 23:25

I think 38Kb it's enough, because to solve this problem with cheating you need only one array [1..6541] of word constans.

Re: you only now got AC.

Posted by ACM.Tolstobrov_Anatoliy[Ivanovo SPU] 20 Mar 2006 00:36

YES YES YES.
i do it.

Re: A easy problem

Posted by xurshid_n 3 Jul 2006 17:12

Please, send me your solution my E-mail: xujand000@rambler.ru

Re: A easy problem

Posted by xurshid_n 3 Jul 2006 17:15

for n are:
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 53
K :
2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45 and 51
is right?

Re: A easy problem

Posted by AlexF 31 Aug 2006 14:49

xurshid_n wrote 3 July 2006 17:15

for n are:
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 53
K :
2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45 and 51
is right?

Yes, it's right!

Re: A easy problem

Posted by esger 8 Dec 2012 13:48

Why the answer for 41 is 35?
if k=35, then doomsday will be 22th attempt. but if k = 39, the repetition will be after 42 sleep.

Re: A easy problem

Posted by Eugene 12 Jun 2014 17:06

Nope. 39^21 == 39^1 mod 41
http://www.wolframalpha.com/input/?i=39%5E21+mod+41

Discussion of Problem 1268. Little Chu