"Your task is to make the largest number of the Great Discoveries and maximally to delay the doomsday." Notice, that we are not only maximazing the period, but also the k^period. So we have to find strictly maximal "generator"/"primitive"/"первообразная"/"образующая". There can be problem with understanding the way of minimizing these values. But as period it divisor of (mod - 1), and there are many generator, and they are quite uniformly distributed, probably k^(mod - 1) will always be better, than some p^((mod - 1) / q), where p > k. Could anybody tell your solution? It asks you to find the maximal primitive root of n 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!!! 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! How to solve this problem by maths? Read "Introduction to Algorithms", chapter 33 - modular arithmetics, group generators, Lagrange theorem, etc. 17 minutes? What kind of so called "smart brute-force"? You can send to fujieyun@163.com to tell me your way. Thanks. Edited by author 09.09.2005 00:20 How did you reach this time? Ok. I submited it. My worked 27 sec. Vladimir Yakovlev(USU) 91501 bytes > 64000 bytes Where rejudge? P.S. I too got AC with cheating [ 38kb ]. I think 38Kb it's enough, because to solve this problem with cheating you need only one array [1..6541] of word constans. Please, send me your solution my E-mail: xujand000@rambler.ru 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? 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! 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. Please, send me your solution or algorithm! my email: xujand000@rambler.ru Please, send me your solution or algorithm! my email: cpp_student@163.com Please, send me your solution or algorithm! my email: ttxxli@163.com Heh, I solved without precalc too, but my solution got time near 0.234 sec (( Please, send me your solution or algorithm! my email: k13795263@126.com Я на java решил за 0.25 без масива .На С++ было бы намного быстрее.Вообще основная идея - первообразный корень по примарному модулю. (Извините за русский но английский я не знаю ) Thank you... Edited by author 12.10.2013 08:56 There are some unobvious things in the statement: 1) k < n, not k <= n 2) if there are many answers exist, you should output the greatest one Maybe it'll help somebody 3 Can the answer be 5 or bigger? Edited by author 09.08.2007 06:10 Edited by author 09.08.2007 06:10 "he can’t sleep more than one week after his birth" Yes k < n Could anyone explain the example input? Why it is 8 ? ( I think 9 is better ) sorry,I misunderstand the problem a[65521]:=65504; a[65519]:=65517; a[65497]:=65490; a[65479]:=65474; a[65449]:=65438; a[65447]:=65445; a[65437]:=65431; a[65423]:=65421; a[65419]:=65414; a[65413]:=65408; a[65407]:=65400; a[65393]:=65390; a[65381]:=65378; a[65371]:=65367; a[65357]:=65355; a[65353]:=65348; a[65327]:=65325; a[65323]:=65319; a[65309]:=65307; a[65293]:=65291; a[65287]:=65285; a[65269]:=65267; a[65267]:=65264; a[65257]:=65252; a[65239]:=65237; a[65213]:=65211; a[65203]:=65199; a[65183]:=65181; a[65179]:=65175; a[65173]:=65171; a[65171]:=65168; a[65167]:=65165; a[65147]:=65144; a[65141]:=65139; a[65129]:=65126; a[65123]:=65120; a[65119]:=65114; a[65111]:=65109; a[65101]:=65099; a[65099]:=65096; a[65089]:=65082; a[65071]:=65069; a[65063]:=65061; a[65053]:=65048; a[65033]:=65030; a[65029]:=65027; a[65027]:=65024; a[65011]:=65007; a[65003]:=64993; a[64997]:=64995; a[64969]:=64956; a[64951]:=64949; a[64937]:=64934; a[64927]:=64918; a[64921]:=64914; a[64919]:=64917; a[64901]:=64899; a[64891]:=64871; a[64879]:=64877; a[64877]:=64874; a[64871]:=64869; a[64853]:=64851; a[64849]:=64836; a[64817]:=64814; a[64811]:=64808; a[64793]:=64790; a[64783]:=64768; a[64781]:=64779; a[64763]:=64760; a[64747]:=64737; a[64717]:=64715; a[64709]:=64706; a[64693]:=64691; a[64679]:=64677; a[64667]:=64664; a[64663]:=64661; a[64661]:=64659; a[64633]:=64628; a[64627]:=64620; a[64621]:=64615; a[64613]:=64611; a[64609]:=64574; a[64601]:=64598; a[64591]:=64589; a[64579]:=64575; a[64577]:=64574; a[64567]:=64565; a[64553]:=64550; a[64513]:=64508; a[64499]:=64496; a[64489]:=64482; a[64483]:=64479; a[64453]:=64451; a[64451]:=64448; a[64439]:=64436; a[64433]:=64430; a[64403]:=64400; a[64399]:=64392; a[64381]:=64379; a[64373]:=64371; a[64333]:=64331; a[64327]:=64325; a[64319]:=64317; a[64303]:=64301; a[64301]:=64299; a[64283]:=64280; a[64279]:=64268; a[64271]:=64269; a[64237]:=64235; a[64231]:=64229; a[64223]:=64221; a[64217]:=64214; a[64189]:=64187; a[64187]:=64184; a[64171]:=64166; a[64157]:=64155; a[64153]:=64148; a[64151]:=64149; a[64123]:=64119; a[64109]:=64107; a[64091]:=64087; a[64081]:=64070; a[64067]:=64064; a[64063]:=64061; a[64037]:=64035; a[64033]:=64028; a[64019]:=64016; a[64013]:=64011; a[64007]:=64005; a[63997]:=63995; a[63977]:=63974; a[63949]:=63947; a[63929]:=63926; a[63913]:=63900; a[63907]:=63903; a[63901]:=63894; a[63863]:=63861; a[63857]:=63854; a[63853]:=63851; a[63841]:=63824; a[63839]:=63837; a[63823]:=63814; a[63809]:=63806; a[63803]:=63800; a[63799]:=63797; a[63793]:=63788; a[63781]:=63779; a[63773]:=63771; a[63761]:=63758; a[63743]:=63741; a[63737]:=63734; a[63727]:=63725; a[63719]:=63717; a[63709]:=63703; a[63703]:=63701; a[63697]:=63692; a[63691]:=63686; a[63689]:=63686; a[63671]:=63668; a[63667]:=63663; a[63659]:=63656; a[63649]:=63642; a[63647]:=63645; a[63629]:=63627; a[63617]:=63614; a[63611]:=63608; a[63607]:=63605; a[63601]:=63594; a[63599]:=63597; a[63589]:=63587; a[63587]:=63584; a[63577]:=63572; a[63559]:=63557; a[63541]:=63539; a[63533]:=63530; a[63527]:=63525; a[63521]:=63518; a[63499]:=63494; a[63493]:=63491; a[63487]:=63478; a[63473]:=63470; a[63467]:=63464; a[63463]:=63461; a[63443]:=63440; a[63439]:=63437; a[63421]:=63419; a[63419]:=63416; a[63409]:=63402; a[63397]:=63395; a[63391]:=63389; a[63389]:=63387; a[63377]:=63374; a[63367]:=63365; a[63361]:=63324; a[63353]:=63350; a[63347]:=63344; a[63337]:=63332; a[63331]:=63327; a[63317]:=63315; a[63313]:=63308; a[63311]:=63309; a[63299]:=63296; a[63281]:=63275; a[63277]:=63275; a[63247]:=63245; a[63241]:=63234; a[63211]:=63205; a[63199]:=63197; a[63197]:=63195; a[63179]:=63175; a[63149]:=63147; a[63131]:=63128; a[63127]:=63118; a[63113]:=63110; a[63103]:=63101; a[63097]:=63092; a[63079]:=63077; a[63073]:=63068; a[63067]:=63063; a[63059]:=63056; a[63031]:=63029; a[63029]:=63027; a[62989]:=62987; a[62987]:=62984; a[62983]:=62972; a[62981]:=62979; a[62971]:=62964; a[62969]:=62966; a[62939]:=62936; a[62929]:=62915; a[62927]:=62925; a[62921]:=62907; a[62903]:=62901; a[62897]:=62894; a[62873]:=62870; a[62869]:=62867; a[62861]:=62858; a[62851]:=62847; a[62827]:=62821; a[62819]:=62816; a[62801]:=62798; a[62791]:=62782; a[62773]:=62768; a[62761]:=62754; a[62753]:=62750; a[62743]:=62732; a[62731]:=62711; a[62723]:=62720; a[62701]:=62699; a[62687]:=62685; a[62683]:=62677; a[62659]:=62653; a[62653]:=62651; a[62639]:=62637; a[62633]:=62630; a[62627]:=62624; a[62617]:=62612; a[62603]:=62600; a[62597]:=62595; a[62591]:=62589; a[62581]:=62579; a[62563]:=62557; a[62549]:=62547; a[62539]:=62535; a[62533]:=62531; a[62507]:=62504; a[62501]:=62499; a[62497]:=62487; a[62483]:=62480; a[62477]:=62475; a[62473]:=62468; a[62467]:=62461; I don't know where, but did you use unsigned int to calculate this array? You can compare with yours: a[62467]:=62461; a[62473]:=62468; a[62477]:=62475; a[62483]:=62480; a[62497]:=62487; a[62501]:=62499; a[62507]:=62504; a[62533]:=62531; a[62539]:=62535; a[62549]:=62547; a[62563]:=62557; a[62581]:=62579; a[62591]:=62589; a[62597]:=62595; a[62603]:=62600; a[62617]:=62612; a[62627]:=62624; a[62633]:=62630; a[62639]:=62637; a[62653]:=62651; a[62659]:=62653; a[62683]:=62677; a[62687]:=62685; a[62701]:=62699; a[62723]:=62720; a[62731]:=62711; a[62743]:=62732; a[62753]:=62750; a[62761]:=62754; a[62773]:=62768; a[62791]:=62782; a[62801]:=62798; a[62819]:=62816; a[62827]:=62821; a[62851]:=62847; a[62861]:=62858; a[62869]:=62867; a[62873]:=62870; a[62897]:=62894; a[62903]:=62901; a[62921]:=62907; a[62927]:=62925; a[62929]:=62915; a[62939]:=62936; a[62969]:=62966; a[62971]:=62964; a[62981]:=62979; a[62983]:=62972; a[62987]:=62984; a[62989]:=62987; a[63029]:=63027; a[63031]:=63029; a[63059]:=63056; a[63067]:=63063; a[63073]:=63068; a[63079]:=63077; a[63097]:=63092; a[63103]:=63101; a[63113]:=63110; a[63127]:=63118; a[63131]:=63128; a[63149]:=63147; a[63179]:=63175; a[63197]:=63195; a[63199]:=63197; a[63211]:=63205; a[63241]:=63234; a[63247]:=63245; a[63277]:=63275; a[63281]:=63275; a[63299]:=63296; a[63311]:=63309; a[63313]:=63308; a[63317]:=63315; a[63331]:=63327; a[63337]:=63332; a[63347]:=63344; a[63353]:=63350; a[63361]:=63324; a[63367]:=63365; a[63377]:=63374; a[63389]:=63387; a[63391]:=63389; a[63397]:=63395; a[63409]:=63402; a[63419]:=63416; a[63421]:=63419; a[63439]:=63437; a[63443]:=63440; a[63463]:=63461; a[63467]:=63464; a[63473]:=63470; a[63487]:=63478; a[63493]:=63491; a[63499]:=63494; a[63521]:=63518; a[63527]:=63525; a[63533]:=63530; a[63541]:=63539; a[63559]:=63557; a[63577]:=63572; a[63587]:=63584; a[63589]:=63587; a[63599]:=63597; a[63601]:=63594; a[63607]:=63605; a[63611]:=63608; a[63617]:=63614; a[63629]:=63627; a[63647]:=63645; a[63649]:=63642; a[63659]:=63656; a[63667]:=63663; a[63671]:=63668; a[63689]:=63686; a[63691]:=63686; a[63697]:=63692; a[63703]:=63701; a[63709]:=63703; a[63719]:=63717; a[63727]:=63725; a[63737]:=63734; a[63743]:=63741; a[63761]:=63758; a[63773]:=63771; a[63781]:=63779; a[63793]:=63788; a[63799]:=63797; a[63803]:=63800; a[63809]:=63806; a[63823]:=63814; a[63839]:=63837; a[63841]:=63824; a[63853]:=63851; a[63857]:=63854; a[63863]:=63861; a[63901]:=63894; a[63907]:=63903; a[63913]:=63900; a[63929]:=63926; a[63949]:=63947; a[63977]:=63974; a[63997]:=63995; a[64007]:=64005; a[64013]:=64011; a[64019]:=64016; a[64033]:=64028; a[64037]:=64035; a[64063]:=64061; a[64067]:=64064; a[64081]:=64070; a[64091]:=64087; a[64109]:=64107; a[64123]:=64119; a[64151]:=64149; a[64153]:=64148; a[64157]:=64155; a[64171]:=64166; a[64187]:=64184; a[64189]:=64187; a[64217]:=64214; a[64223]:=64221; a[64231]:=64229; a[64237]:=64235; a[64271]:=64269; a[64279]:=64268; a[64283]:=64280; a[64301]:=64299; a[64303]:=64301; a[64319]:=64317; a[64327]:=64325; a[64333]:=64331; a[64373]:=64371; a[64381]:=64379; a[64399]:=64392; a[64403]:=64400; a[64433]:=64430; a[64439]:=64436; a[64451]:=64448; a[64453]:=64451; a[64483]:=64479; a[64489]:=64482; a[64499]:=64496; a[64513]:=64508; a[64553]:=64550; a[64567]:=64565; a[64577]:=64574; a[64579]:=64575; a[64591]:=64589; a[64601]:=64598; a[64609]:=64574; a[64613]:=64611; a[64621]:=64615; a[64627]:=64620; a[64633]:=64628; a[64661]:=64659; a[64663]:=64661; a[64667]:=64664; a[64679]:=64677; a[64693]:=64691; a[64709]:=64706; a[64717]:=64715; a[64747]:=64737; a[64763]:=64760; a[64781]:=64779; a[64783]:=64768; a[64793]:=64790; a[64811]:=64808; a[64817]:=64814; a[64849]:=64836; a[64853]:=64851; a[64871]:=64869; a[64877]:=64874; a[64879]:=64877; a[64891]:=64871; a[64901]:=64899; a[64919]:=64917; a[64921]:=64914; a[64927]:=64918; a[64937]:=64934; a[64951]:=64949; a[64969]:=64956; a[64997]:=64995; a[65003]:=64993; a[65011]:=65007; a[65027]:=65024; a[65029]:=65027; a[65033]:=65030; a[65053]:=65048; a[65063]:=65061; a[65071]:=65069; a[65089]:=65082; a[65099]:=65096; a[65101]:=65099; a[65111]:=65109; a[65119]:=65114; a[65123]:=65120; a[65129]:=65126; a[65141]:=65139; a[65147]:=65144; a[65167]:=65165; a[65171]:=65168; a[65173]:=65171; a[65179]:=65175; a[65183]:=65181; a[65203]:=65199; a[65213]:=65211; a[65239]:=65237; a[65257]:=65252; a[65267]:=65264; a[65269]:=65267; a[65287]:=65285; a[65293]:=65291; a[65309]:=65307; a[65323]:=65319; a[65327]:=65325; a[65353]:=65348; a[65357]:=65355; a[65371]:=65367; a[65381]:=65378; a[65393]:=65390; a[65407]:=65400; a[65413]:=65408; a[65419]:=65414; a[65423]:=65421; a[65437]:=65431; a[65447]:=65445; a[65449]:=65438; a[65479]:=65474; a[65497]:=65490; a[65519]:=65517; a[65521]:=65504; P.S. If you still have WA(2) mail your program to dimanyes@mail.ru - I'll try to help you (though I do it very rarely). Edited by author 27.08.2004 16:17 - Can you give me the result of a[2]..a[1000]? Edited by author 01.09.2004 19:59 What does "the largest number of the Great Discoveries" mean? And what does "maximally to delay the doomsday" mean? If there are more than one solution, which K should I output? Any K or the biggest K? Give me some test If you can. Thanks It means that you should output the biggest K. maybe not the best but it was a 0.14 sec solution with NO PREGENERATION maybe it's not a big deal but i had a lot a lot of problems about 30 bad submits caused by using long not unsigned long "Your task is to make the largest number of the Great Discoveries and maximally to delay the doomsday" What does "largest number of the Great Discoveries" mean ? you go to K, K^2, K^3, K^4 and so on, all this modulo N. You stop when you find a value that was before. Maximize this means to find a K so that this "collision" appears later... Oh , I see . I misunderstood it . Thank you for your help ! Edited by author 08.04.2004 10:46 |
|