Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Statement | Igor Parfenov | 1268. Маленький Чу | 18 фев 2023 01:48 | 1 | "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. | How to solve this problem without cheating? | tantian | 1268. Маленький Чу | 17 июн 2020 10:46 | 4 | Could anybody tell your solution? It asks you to find the maximal primitive root of n | Solution | 2ch | 1268. Маленький Чу | 11 фев 2018 01:49 | 1 | | A easy problem | liuchang | 1268. Маленький Чу | 12 июн 2014 17:06 | 17 | 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. | I've got AC without precalculating array ... 0.046 sec | Tolstiy_BSU | 1268. Маленький Чу | 12 окт 2013 08:53 | 11 | 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 | Some clarification | Borozdin Kirill [Psych Up club] | 1268. Маленький Чу | 4 окт 2012 18:57 | 1 | 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 | Is the k must smaller than n? | tantian | 1268. Маленький Чу | 10 авг 2007 06:25 | 4 | 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 | No subject | xiao | 1268. Маленький Чу | 20 июл 2006 08:48 | 3 | Could anyone explain the example input? Why it is 8 ? ( I think 9 is better ) sorry,I misunderstand the problem | here some part of a const array... I had WA on test 2... Were i was wrong? | LeXuS[Alex Kalugin] | 1268. Маленький Чу | 1 сен 2004 19:58 | 10 | 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 | Question about the meaning of this problem? | Saturn | 1268. Маленький Чу | 31 июл 2004 15:37 | 3 | 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. | i managed to find a solution | marius dumitran | 1268. Маленький Чу | 5 май 2004 14:38 | 2 | 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 | A question about the meaning of this problem | XueMao | 1268. Маленький Чу | 8 апр 2004 10:42 | 3 | "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 |
|
|