oj.uz

Submission #15223

# Submission time Handle Problem Language Result Execution time Memory
15223 2015-07-12T04:08:26 Z progressive 피보나미얼 (kriii3_V) C++14
74 / 74
 2 ms 1132 KB 
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long ans[1010];
int rem[1010];
int fib[10100];
long long go(int N,int K)
{
	int cyc=0;
	fib[0]=0;
	fib[1]=1;
	for(int i=2;;i++)
	{
		fib[i]=fib[i-1]+fib[i-2];
		fib[i]%=K;
		if(fib[i]==0)
		{
			cyc=i;
			break;
		} 
	}
	N/=cyc;
	long long ans=0;
	if(K==2) ans+=N/2;
	while(N!=0)
	{
		ans+=N;
		N/=K;
	}
	return ans;
}
int main()
{
	int N,K;
	scanf("%d%d",&N,&K);
	for(int i=2;i<=K;i++)
	{
		bool isp=true;
		int k=i;
		memset(rem,0,sizeof(rem));
		for(int j=2;j<k;j++)
		{
			if(k%j==0)
			{
				k/=j;
				rem[j]++;
				j--;
				isp=false;
			}
		}
		if(k!=1) rem[k]++;
		if(isp)
			ans[i]=go(N,i);
		else
		{
			ans[i]=987654321987654321LL;
			for(int j=2;j<=i;j++)
				if(rem[j])
					ans[i]=min(ans[i],ans[j]/rem[j]);
		}
		printf("%lld\n",ans[i]);
	}
}

Subtask #1
32.0 / 32.0

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

Subtask #2
42.0 / 42.0

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