oj.uz

답안 #15350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15350 2015-07-12T06:30:25 Z tonyjjw 피보나미얼 (kriii3_V) C++
32 / 74
 431 ms 1092 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -