Submission #15366

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15366	2015-07-12T06:47:50 Z	tonyjjw	피보나미얼 (kriii3_V)	C++	74 / 74	88 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){
				if(k<10){
				for(l=k;l<=n;l+=k){
					if(fibmod(l,j)==0)break;
				}
				}
				else l=k*i;
				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	4 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	49 ms	1092 KB	Output is correct
8	Correct	77 ms	1092 KB	Output is correct
9	Correct	88 ms	1092 KB	Output is correct
10	Correct	87 ms	1092 KB	Output is correct

Subtask #2

42.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	1092 KB	Output is correct
2	Correct	87 ms	1092 KB	Output is correct
3	Correct	87 ms	1092 KB	Output is correct
4	Correct	88 ms	1092 KB	Output is correct
5	Correct	87 ms	1092 KB	Output is correct
6	Correct	88 ms	1092 KB	Output is correct
7	Correct	83 ms	1092 KB	Output is correct
8	Correct	84 ms	1092 KB	Output is correct
9	Correct	88 ms	1092 KB	Output is correct
10	Correct	87 ms	1092 KB	Output is correct