oj.uz

Submission #15451

# Submission time Handle Problem Language Result Execution time Memory
15451 2015-07-12T07:53:43 Z ggoh 피보나미얼 (kriii3_V) C++
32 / 74
 2000 ms 1108 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;

	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 0 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 0 ms 1108 KB Output is correct
5 Correct 0 ms 1108 KB Output is correct
6 Correct 0 ms 1108 KB Output is correct
7 Correct 0 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 0 ms 1108 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct

Subtask #2
0.0 / 42.0

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