글 읽기 - 1456번 어디가 틀린 것인지 잘 모르겟습니다.....

20151571 1년 전 0

어디가 틀렸는지 전혀 감이 오지 않습니다.......

a,b의 범위가 10^14이므로 소수는 10^7까지만 구하고

곱셈에서 오버플로우가 나올까봐 b에서 한번 소수를 나눈채로 구해주었습니다.

혹시나 싶어서 오버플로우가 나올 까봐 if문에서 if(sum>INF) break;

문을 추가하여보았는데도 틀렸습니다가 뜨네요 ㄷㄷ.......

틀린 테스트 케이스가 있을까요...?

											#include <cstdio>
#define min(a,b)	((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
ll max = 10000000;//최대 10^7까지 소수를 구해준다.
const long long INF = 100000000000000LL;//최대가 될 수 있는 경우
int main(){
   bool t[10000001];//소수인지 아닌지 확인해준다.
   int ans=0,cnt=0;
   ll a,b;
   ll p[1000001];
   scanf("%lld %lld",&a,&b);
   max = min(max,b);//b가 10^7보다 큰경우 10^7까지 소수를 구해준다.
   for(int i=2;i<=max;i++)
      t[i]=true;

   for(int i=2;i<=max;i++){
      if(!t[i])
	 continue;
      	p[cnt++]=i;
      for(int j=i+i;j<=max;j+=i)
	 t[j]=false;
   }
   for(int i=0;i<cnt;i++){
      ll sum=p[i];
      while(sum<=b/p[i]){//오버 플로우가 날 수 있으므로 한번 나눠준것으로 계산한다.
	if(sum>=a)//a보다 큰 경우에만 더해준다.
	  ans++;
	sum*=p[i];
      }
   }
   printf("%d\n",ans);
   return 0;
}
										

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ACM-ICPC

1456번 어디가 틀린 것인지 잘 모르겟습니다.....

20151571 1년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

앱