oj.uz

답안 #15366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15366 2015-07-12T06:47:50 Z tonyjjw 피보나미얼 (kriii3_V) C++
74 / 74
 88 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){
				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

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

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