Submission #15558

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15558	2015-07-12T13:59:43 Z	ggoh	피보나미얼 (kriii3_V)	C++	74 / 74	2 ms	1304 KB

V

#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][333];
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;
	for(i=1;p[i]&&p[i]<=c;i++)
	{
		y=1;z=0;
		for(j=2;j;j++)
		{
			x=y+z;
			x%=p[i];
			if(x==0)
			{
				g[i][0]=j;
				break;
			}
			z=y;
			y=x;
		}
		b=0;
		while(g[i][b]<=a/p[i])
		{
			g[i][b+1]=g[i][b]*p[i];
			b++;
		}
	}
	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]<=c;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]<=c;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	1304 KB	Output is correct
2	Correct	0 ms	1304 KB	Output is correct
3	Correct	0 ms	1304 KB	Output is correct
4	Correct	0 ms	1304 KB	Output is correct
5	Correct	0 ms	1304 KB	Output is correct
6	Correct	2 ms	1304 KB	Output is correct
7	Correct	0 ms	1304 KB	Output is correct
8	Correct	2 ms	1304 KB	Output is correct
9	Correct	0 ms	1304 KB	Output is correct
10	Correct	0 ms	1304 KB	Output is correct

Subtask #2

42.0 / 42.0

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