Submission #15350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15350	2015-07-12T06:30:25 Z	tonyjjw	피보나미얼 (kriii3_V)	C++	32 / 74	431 ms	1092 KB

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.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1092 KB	Output is correct
2	Correct	7 ms	1092 KB	Output is correct
3	Correct	7 ms	1092 KB	Output is correct
4	Correct	8 ms	1092 KB	Output is correct
5	Correct	8 ms	1092 KB	Output is correct
6	Correct	8 ms	1092 KB	Output is correct
7	Correct	46 ms	1092 KB	Output is correct
8	Correct	74 ms	1092 KB	Output is correct
9	Correct	91 ms	1092 KB	Output is correct
10	Correct	92 ms	1092 KB	Output is correct

Subtask #2

0.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	1092 KB	Output is correct
2	Correct	113 ms	1092 KB	Output is correct
3	Correct	102 ms	1092 KB	Output is correct
4	Correct	109 ms	1092 KB	Output is correct
5	Correct	125 ms	1092 KB	Output is correct
6	Correct	268 ms	1092 KB	Output is correct
7	Correct	277 ms	1092 KB	Output is correct
8	Incorrect	431 ms	1092 KB	Output isn't correct
9	Halted	0 ms	0 KB	-