Submission #15350

#	Time	Username	Problem	Language	Result	Execution time	Memory
15350		tonyjjw	피보나미얼 (kriii3_V)	C++98	32 / 74	431 ms	1092 KiB

V

#include<stdio.h>
long long int n,m;
long long int dp[1010];
long long int fibmod(long long int x,long long int y){
	long long int i,j,k,t;
	j=0;
	k=1;
	for(i=61;i>=0;i--){
		t=j*j+k*k;
		j=j*k+j*(k-j);
		k=t;
		j%=y;
		k%=y;
		if((x>>(int)i)%2!=0){
			t=j+k;
			j=k;
			k=t%y;
		}
	}
	return j;
}
int main(){
	long long int i,j,k,l;
	scanf("%lld%lld",&n,&m);
	for(i=2;i<=m;i++){
		for(j=2;j<i;j++){
			if(i%j==0)break;
		}
		if(j==i){
			k=1;
			for(j=i;;j*=i){
				for(l=k;l<=n;l+=k){
					if(fibmod(l,j)==0)break;
				}
				if(l>n)break;
				dp[i]+=n/l;
				k=l;
			}
			printf("%lld\n",dp[i]);
		}
		else{
			dp[i]=5999999999999999LL;
			k=i;
			for(j=2;k!=1;j++){
				l=0;
				if(k%j==0){
					while(k%j==0){
						k/=j;
						l++;
					}
					if(dp[i]>dp[j]/l)dp[i]=dp[j]/l;
				}
			}
			printf("%lld\n",dp[i]);
		}
	}
}

• Subtask 1: 32 / 32
• Subtask 2: 0 / 42