Submission #15223

#	Time	Username	Problem	Language	Result	Execution time	Memory
15223		progressive	피보나미얼 (kriii3_V)	C++14	74 / 74	2 ms	1132 KiB

V

#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 / 32
• Subtask 2: 42 / 42