oj.uz

Submission #15447

# Submission time Handle Problem Language Result Execution time Memory
15447 2015-07-12T07:49:29 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);
	for(i=0;p[i];i++)
	{
		b=1;
		for(k=0;1;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 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 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 2 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 4 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 27 ms 1108 KB Output is correct
3 Correct 13 ms 1108 KB Output is correct
4 Correct 22 ms 1108 KB Output is correct
5 Correct 48 ms 1108 KB Output is correct
6 Execution timed out 2000 ms 1104 KB Program timed out
7 Halted 0 ms 0 KB -