oj.uz

Submission #15531

# Submission time Handle Problem Language Result Execution time Memory
15531 2015-07-12T08:55:05 Z ggoh 피보나미얼 (kriii3_V) C++
32 / 74
 2000 ms 1112 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
int a,b,c,i,j,k,x,y,z;
int p[169]={2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 
101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 
193 , 197 , 199 , 211 , 223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 , 283 , 
293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 
409 , 419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , 461 , 463 , 467 , 479 , 487 , 491 , 499 , 503 , 509 , 
521 , 523 , 541 , 547 , 557 , 563 , 569 , 571 , 577 , 587 , 593 , 599 , 601 , 607 , 613 , 617 , 619 , 631 , 
641 , 643 , 647 , 653 , 659 , 661 , 673 , 677 , 683 , 691 , 701 , 709 , 719 , 727 , 733 , 739 , 743 , 751 , 
757 , 761 , 769 , 773 , 787 , 797 , 809 , 811 , 821 , 823 , 827 , 829 , 839 , 853 , 857 , 859 , 863 , 877 , 
881 , 883 , 887 , 907 , 911 , 919 , 929 , 937 , 941 , 947 , 953 , 967 , 971 , 977 , 983 , 991 , 997};
int g[169][33];
int wh[169],u,m,ch,e[169];
main()
{
	scanf("%d%d",&a,&c);
g[0][0]=3;g[0][1]=6;g[0][2]=6;g[0][3]=12;g[0][4]=24;g[0][5]=48;g[0][6]=96;g[0][7]=192;g[0][8]=384;g[0][9]=768;g[0][10]=1536;g[0][11]=3072;g[0][12]=6144;g[0][13]=12288;g[0][14]=24576;g[0][15]=49152;g[0][16]=98304;g[0][17]=196608;g[0][18]=393216;g[0][19]=786432;g[0][20]=1572864;g[0][21]=3145728;g[0][22]=6291456;g[0][23]=12582912;g[0][24]=25165824;g[0][25]=50331648;g[0][26]=100663296;g[0][27]=201326592;g[0][28]=402653184;g[0][29]=805306368;g[1][0]=4;g[1][1]=12;g[1][2]=36;g[1][3]=108;g[1][4]=324;g[1][5]=972;g[1][6]=2916;g[1][7]=8748;g[1][8]=26244;g[1][9]=78732;g[1][10]=236196;g[1][11]=708588;g[1][12]=2125764;g[1][13]=6377292;g[1][14]=19131876;g[1][15]=57395628;g[1][16]=172186884;g[1][17]=516560652;g[2][0]=5;g[2][1]=25;g[2][2]=125;g[2][3]=625;g[2][4]=3125;g[2][5]=15625;g[2][6]=78125;g[2][7]=390625;g[2][8]=1953125;g[2][9]=9765625;g[2][10]=48828125;g[2][11]=244140625;g[3][0]=8;g[3][1]=56;g[3][2]=392;g[3][3]=2744;g[3][4]=19208;g[3][5]=134456;g[3][6]=941192;g[3][7]=6588344;g[3][8]=46118408;g[3][9]=322828856;g[4][0]=10;g[4][1]=110;g[4][2]=1210;g[4][3]=13310;g[4][4]=146410;g[4][5]=1610510;g[4][6]=17715610;g[4][7]=194871710;g[5][0]=7;g[5][1]=91;g[5][2]=1183;g[5][3]=15379;g[5][4]=199927;g[5][5]=2599051;g[5][6]=33787663;g[5][7]=439239619;g[6][0]=9;g[6][1]=153;g[6][2]=2601;g[6][3]=44217;g[6][4]=751689;g[6][5]=12778713;g[6][6]=217238121;g[7][0]=18;g[7][1]=342;g[7][2]=6498;g[7][3]=123462;g[7][4]=2345778;g[7][5]=44569782;g[7][6]=846825858;g[8][0]=24;g[8][1]=552;g[8][2]=12696;g[8][3]=292008;g[8][4]=6716184;g[8][5]=154472232;g[9][0]=14;g[9][1]=406;g[9][2]=11774;g[9][3]=341446;g[9][4]=9901934;g[9][5]=287156086;g[10][0]=30;g[10][1]=930;g[10][2]=28830;g[10][3]=893730;g[10][4]=27705630;g[10][5]=858874530;g[11][0]=19;g[11][1]=703;g[11][2]=26011;g[11][3]=962407;g[11][4]=35609059;g[12][0]=20;g[12][1]=820;g[12][2]=33620;g[12][3]=1378420;g[12][4]=56515220;g[13][0]=44;g[13][1]=1892;g[13][2]=81356;g[13][3]=3498308;g[13][4]=150427244;g[14][0]=16;g[14][1]=752;g[14][2]=35344;g[14][3]=1661168;g[14][4]=78074896;g[15][0]=27;g[15][1]=1431;g[15][2]=75843;g[15][3]=4019679;g[15][4]=213042987;g[16][0]=58;g[16][1]=3422;g[16][2]=201898;g[16][3]=11911982;g[16][4]=702806938;g[17][0]=15;g[17][1]=915;g[17][2]=55815;g[17][3]=3404715;g[17][4]=207687615;g[18][0]=68;g[18][1]=4556;g[18][2]=305252;g[18][3]=20451884;g[19][0]=70;g[19][1]=4970;g[19][2]=352870;g[19][3]=25053770;g[20][0]=37;g[20][1]=2701;g[20][2]=197173;g[20][3]=14393629;g[21][0]=78;g[21][1]=6162;g[21][2]=486798;g[21][3]=38457042;g[22][0]=84;g[22][1]=6972;g[22][2]=578676;g[22][3]=48030108;g[23][0]=11;g[23][1]=979;g[23][2]=87131;g[23][3]=7754659;g[23][4]=690164651;g[24][0]=49;g[24][1]=4753;g[24][2]=461041;g[24][3]=44720977;g[25][0]=50;g[25][1]=5050;g[25][2]=510050;g[25][3]=51515050;g[26][0]=104;g[26][1]=10712;g[26][2]=1103336;g[26][3]=113643608;g[27][0]=36;g[27][1]=3852;g[27][2]=412164;g[27][3]=44101548;g[28][0]=27;g[28][1]=2943;g[28][2]=320787;g[28][3]=34965783;g[29][0]=19;g[29][1]=2147;g[29][2]=242611;g[29][3]=27415043;g[30][0]=128;g[30][1]=16256;g[30][2]=2064512;g[30][3]=262193024;g[31][0]=130;g[31][1]=17030;g[31][2]=2230930;g[31][3]=292251830;g[32][0]=69;g[32][1]=9453;g[32][2]=1295061;g[32][3]=177423357;g[33][0]=46;g[33][1]=6394;g[33][2]=888766;g[33][3]=123538474;g[34][0]=37;g[34][1]=5513;g[34][2]=821437;g[34][3]=122394113;g[35][0]=50;g[35][1]=7550;g[35][2]=1140050;g[35][3]=172147550;g[36][0]=79;g[36][1]=12403;g[36][2]=1947271;g[36][3]=305721547;g[37][0]=164;g[37][1]=26732;g[37][2]=4357316;g[37][3]=710242508;g[38][0]=168;g[38][1]=28056;g[38][2]=4685352;g[38][3]=782453784;g[39][0]=87;g[39][1]=15051;g[39][2]=2603823;g[39][3]=450461379;g[40][0]=178;g[40][1]=31862;g[40][2]=5703298;g[41][0]=90;g[41][1]=16290;g[41][2]=2948490;g[41][3]=533676690;g[42][0]=190;g[42][1]=36290;g[42][2]=6931390;

g[43][0]=97;g[43][1]=18721;g[43][2]=3613153;g[43][3]=697338529;g[44][0]=99;g[44][1]=19503;g[44][2]=3842091;g[44][3]=756891927;g[45][0]=22;g[45][1]=4378;g[45][2]=871222;g[45][3]=173373178;g[46][0]=42;g[46][1]=8862;g[46][2]=1869882;g[46][3]=394545102;g[47][0]=224;g[47][1]=49952;g[47][2]=11139296;g[48][0]=228;g[48][1]=51756;g[48][2]=11748612;g[49][0]=114;g[49][1]=26106;g[49][2]=5978274;g[50][0]=13;g[50][1]=3029;g[50][2]=705757;g[50][3]=164441381;g[51][0]=238;g[51][1]=56882;g[51][2]=13594798;g[52][0]=120;g[52][1]=28920;g[52][2]=6969720;g[53][0]=250;g[53][1]=62750;g[53][2]=15750250;g[54][0]=129;g[54][1]=33153;g[54][2]=8520321;g[55][0]=88;g[55][1]=23144;g[55][2]=6086872;g[56][0]=67;g[56][1]=18023;g[56][2]=4848187;g[57][0]=270;g[57][1]=73170;g[57][2]=19829070;g[58][0]=139;g[58][1]=38503;g[58][2]=10665331;g[59][0]=28;g[59][1]=7868;g[59][2]=2210908;g[59][3]=621265148;g[60][0]=284;g[60][1]=80372;g[60][2]=22745276;g[61][0]=147;g[61][1]=43071;g[61][2]=12619803;g[62][0]=44;g[62][1]=13508;g[62][2]=4146956;g[63][0]=310;g[63][1]=96410;g[63][2]=29983510;g[64][0]=157;g[64][1]=49141;g[64][2]=15381133;g[65][0]=159;g[65][1]=50403;g[65][2]=15977751;g[66][0]=110;g[66][1]=36410;g[66][2]=12051710;g[67][0]=169;g[67][1]=56953;g[67][2]=19193161;g[68][0]=116;g[68][1]=40252;g[68][2]=13967444;g[69][0]=174;g[69][1]=60726;g[69][2]=21193374;g[70][0]=59;g[70][1]=20827;g[70][2]=7351931;g[71][0]=358;g[71][1]=128522;g[71][2]=46139398;g[72][0]=368;g[72][1]=135056;g[72][2]=49565552;g[73][0]=187;g[73][1]=69751;g[73][2]=26017123;g[74][0]=378;g[74][1]=143262;g[74][2]=54296298;g[75][0]=384;g[75][1]=147072;g[75][2]=56328576;g[76][0]=97;g[76][1]=37733;g[76][2]=14678137;g[77][0]=199;g[77][1]=79003;g[77][2]=31364191;g[78][0]=100;g[78][1]=40100;g[78][2]=16080100;g[79][0]=204;g[79][1]=83436;g[79][2]=34125324;g[80][0]=418;g[80][1]=175142;g[80][2]=73384498;g[81][0]=21;g[81][1]=8841;g[81][2]=3722061;g[82][0]=430;g[82][1]=185330;g[82][2]=79877230;g[83][0]=217;g[83][1]=93961;g[83][2]=40685113;g[84][0]=438;g[84][1]=192282;g[84][2]=84411798;g[85][0]=444;g[85][1]=196692;g[85][2]=87134556;g[86][0]=224;g[86][1]=100576;g[86][2]=45158624;g[87][0]=229;g[87][1]=104653;g[87][2]=47826421;g[88][0]=46;g[88][1]=21206;g[88][2]=9775966;g[89][0]=464;g[89][1]=214832;g[89][2]=99467216;g[90][0]=468;g[90][1]=218556;g[90][2]=102065652;g[91][0]=478;g[91][1]=228962;g[91][2]=109672798;g[92][0]=488;g[92][1]=237656;g[92][2]=115738472;g[93][0]=490;g[93][1]=240590;g[93][2]=118129690;g[94][0]=498;g[94][1]=248502;g[94][2]=124002498;g[95][0]=504;g[95][1]=253512;g[95][2]=127516536;g[96][0]=254;g[96][1]=129286;g[96][2]=65806574;g[97][0]=26;g[97][1]=13546;g[97][2]=7057466;g[98][0]=524;g[98][1]=274052;g[98][2]=143329196;g[99][0]=90;g[99][1]=48690;g[99][2]=26341290;g[100][0]=548;g[100][1]=299756;g[100][2]=163966532;g[101][0]=31;g[101][1]=17267;g[101][2]=9617719;g[102][0]=188;g[102][1]=105844;g[102][2]=59590172;g[103][0]=284;g[103][1]=161596;g[103][2]=91948124;g[104][0]=570;g[104][1]=325470;g[104][2]=185843370;g[105][0]=289;g[105][1]=166753;g[105][2]=96216481;g[106][0]=588;g[106][1]=345156;g[106][2]=202606572;g[107][0]=297;g[107][1]=176121;g[107][2]=104439753;g[108][0]=598;g[108][1]=358202;g[108][2]=214562998;g[109][0]=300;g[109][1]=180300;g[109][2]=108360300;g[110][0]=608;g[110][1]=369056;g[110][2]=224016992;g[111][0]=307;g[111][1]=188191;g[111][2]=115361083;g[112][0]=309;g[112][1]=190653;g[112][2]=117632901;g[113][0]=206;g[113][1]=127514;g[113][2]=78931166;g[114][0]=630;g[114][1]=397530;g[114][2]=250841430;g[115][0]=320;g[115][1]=205120;g[115][2]=131481920;g[116][0]=644;g[116][1]=414092;g[116][2]=266261156;g[117][0]=648;g[117][1]=419256;g[117][2]=271258632;g[118][0]=327;g[118][1]=213531;g[118][2]=139435743;g[119][0]=658;g[119][1]=433622;g[119][2]=285756898;g[120][0]=55;g[120][1]=36355;g[120][2]=24030655;g[121][0]=337;g[121][1]=226801;g[121][2]=152637073;g[122][0]=113;g[122][1]=76501;g[122][2]=51791177;g[123][0]=684;g[123][1]=467172;g[123][2]=319078476;g[124][0]=138;g[124][1]=95358;g[124][2]=65892378;g[125][0]=175;g[125][1]=122675;g[125][2]=85995175;g[126][0]=118;g[126][1]=83662;g[126][2]=59316358;g[127][0]=718;g[127][1]=516242;g[127][2]=371177998;g[128][0]=728;g[128][1]=529256;g[128][2]=384769112;g[129][0]=367;g[129][1]=269011;g[129][2]=197185063;g[130][0]=738;g[130][1]=545382;g[130][2]=403037298;g[131][0]=248;g[131][1]=184264;g[131][2]=136908152;g[132][0]=750;g[132][1]=563250;g[132][2]=423000750;g[133][0]=379;g[133][1]=286903;g[133][2]=217185571;g[134][0]=95;g[134][1]=72295;g[134][2]=55016495;g[135][0]=96;g[135][1]=73824;g[135][2]=56770656;g[136][0]=387;g[136][1]=299151;g[136][2]=231243723;g[137][0]=788;g[137][1]=620156;g[137][2]=488062772;g[138][0]=57;g[138][1]=45429;g[138][2]=36206913;g[139][0]=202;g[139][1]=163418;g[139][2]=132205162;g[140][0]=270;g[140][1]=218970;g[140][2]=177584670;g[141][0]=205;g[141][1]=168305;g[141][2]=138178405;g[142][0]=824;g[142][1]=678152;g[142][2]=558119096;g[143][0]=828;g[143][1]=684756;g[143][2]=566293212;g[144][0]=69;g[144][1]=57201;g[144][2]=47419629;g[145][0]=838;g[145][1]=703082;g[145][2]=589885798;g[146][0]=427;g[146][1]=364231;g[146][2]=310689043;g[147][0]=429;g[147][1]=367653;g[147][2]=315078621;g[148][0]=78;g[148][1]=67002;g[148][2]=57554718;g[149][0]=864;g[149][1]=745632;g[149][2]=643480416;g[150][0]=439;g[150][1]=385003;g[150][2]=337647631;g[151][0]=88;g[151][1]=77528;g[151][2]=68302168;g[152][0]=884;g[152][1]=780572;g[152][2]=689245076;g[153][0]=888;g[153][1]=787656;g[153][2]=698650872;g[154][0]=908;g[154][1]=823556;g[154][2]=746965292;g[155][0]=70;g[155][1]=63770;g[155][2]=58094470;g[156][0]=102;g[156][1]=93738;g[156][2]=86145222;g[157][0]=464;g[157][1]=431056;g[157][2]=400451024;g[158][0]=469;g[158][1]=439453;g[158][2]=411767461;g[159][0]=470;g[159][1]=442270;g[159][2]=416176070;g[160][0]=948;g[160][1]=897756;g[160][2]=850174932;g[161][0]=53;g[161][1]=50509;g[161][2]=48135077;g[162][0]=88;g[162][1]=85096;g[162][2]=82287832;g[163][0]=970;g[163][1]=941870;g[163][2]=914555770;g[164][0]=163;g[164][1]=159251;g[164][2]=155588227;g[165][0]=984;g[165][1]=967272;g[165][2]=950828376;g[166][0]=198;g[166][1]=196218;g[166][2]=194452038;g[167][0]=499;g[167][1]=497503;g[167][2]=496010491;	
	for(i=0;p[i];i++)
	{
		b=1;
		for(k=0;k<=2;k++)
		{
			z=0;
			y=1;	
			ch=0;
			b*=p[i];
		for(j=2;j<=a;j++)
		{
			x=y+z;
			x%=b;
			if(x==0)
			{
				g[i][k]=j;
				ch=1;
				break;
			}
			z=y;
			y=x;
		}
			if(ch==0)
			{
				break;
			}
		}
	}
	for(i=0;p[i]&&p[i]<=c;i++)
	{
		for(j=0;g[i][j];j++)
		{
			wh[i]+=a/g[i][j];
		}
	}
	
	for(i=2;i<=c;i++)
	{
		for(j=0;p[j]&&p[j]<=b;j++)e[j]=0;
		u=i;
		m=1e9;
		for(j=0;u!=1;j++)
		{
			while(u%p[j]==0)
			{
				u/=p[j];
				e[j]++;
			}
		}
		for(j=0;p[j]&&p[j]<=b;j++)
		{
			if(e[j])
			{
				m=std::min(m,wh[j]/e[j]);
			}
		}
		printf("%d\n",m);
	}
	
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 0 ms 1112 KB Output is correct
3 Correct 0 ms 1112 KB Output is correct
4 Correct 0 ms 1112 KB Output is correct
5 Correct 0 ms 1112 KB Output is correct
6 Correct 0 ms 1112 KB Output is correct
7 Correct 0 ms 1112 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct
10 Correct 4 ms 1112 KB Output is correct

Subtask #2
0.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1112 KB Output is correct
2 Correct 26 ms 1112 KB Output is correct
3 Correct 13 ms 1112 KB Output is correct
4 Correct 21 ms 1112 KB Output is correct
5 Correct 45 ms 1112 KB Output is correct
6 Execution timed out 2000 ms 1108 KB Program timed out
7 Halted 0 ms 0 KB -