| Show all threads Hide all threads Show all messages Hide all messages | | Statement | Igor Parfenov | 1268. Little Chu | 18 Feb 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. Little Chu | 17 Jun 2020 10:46 | 4 | Could anybody tell your solution? It asks you to find the maximal primitive root of n | | Solution | 2ch | 1268. Little Chu | 11 Feb 2018 01:49 | 1 | | | A easy problem | liuchang | 1268. Little Chu | 12 Jun 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. Little Chu | 12 Oct 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. Little Chu | 4 Oct 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. Little Chu | 10 Aug 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. Little Chu | 20 Jul 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. Little Chu | 1 Sep 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. Little Chu | 31 Jul 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. Little Chu | 5 May 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. Little Chu | 8 Apr 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 |
|
|
