글 읽기 - 1456번 질문

kimsy96 5년 전 0

거의 소수라는 조건 때문에 전체제한의 루트값(10^7) 까지만 에라토스테네스의 체를 이용해서 처리한다음 풀어야 한다는 거 까지는 잡았습니다.

구해놓은 소수에 대하여 구간 a,b안에 들어가는 거의소수를 구하는 과정에서 오버플로우를 방지하는게 문제의 핵심인거 같은데..

제 나름대로 시도를 해봤지만 실패했습니다.

논리적으로 조금 엉성하다고 생각은 하지만

if(next/now!=i) break; 요 부분에서 만약오버플로우가 발생했다면 값이 뒤틀려서 저 조건식을 만족하지 못할 것이라고 생각했습니다.

조금 도와주셨으면 합니다

#include <bits/stdc++.h>
using namespace std;



typedef long long ll;
bool isprime[10000001];

int main()
{
    isprime[1]=true;
    for(int i=2;i<=10000000;i++)
    {
        if(isprime[i])
            continue;
        for(int j=i+i;j<=10000000;j+=i)
            isprime[j]=true;
    }
    ll a,b;
    cin>>a>>b;


    int cnt=0;
    for(int i=2;i<=10000000;i++){
        if(isprime[i])
            continue;
        ll now,next;
        now=1LL*i*i;
        while(1)
        {
            if(now>b)
                break;

            if(a<=now && now<=b)
                cnt++;
            next=1LL*i*now;
            if(next/now!=i)
                break;
            now=next;
        }
    }
    cout<<cnt;
    return 0;

}

kimsy96 5년 전 0

....?

next/now!=i 요 부분을

next%now!=0 으로 고치니까 맞네요.. ;

저렇게 캐치하면 안되는 이유는 뭘까요

kimsy96 5년 전 0

제풀이를 저도 잘 모르겠네요

next%now!=0 이걸로 오버플로우가 잡힌다고 생각했는데.. 안잡힐수도 있지않나요?

kimsy96 5년 전 0

요게 ac받은 소스코드...

질문을 요약하자면

첫번째 WA받은 풀이의 오버플로우 판별 next/now!=i 이 안되는 이유(이건 어렴풋이 알듯합니다 그래도 갓갓분들의 명쾌한 설명이 듣고싶습니다)

두번째 AC받은 밑의 풀이의 오버플로우 판별법 if(next%now!=0) break; 오버플로우되서 값이 어디로 튀느냐에 따라 저걸로 판별못하는 상황이 발생하지않을까요?

#include <bits/stdc++.h>
using namespace std;



typedef long long ll;
bool isprime[10000001];

int main()
{
    isprime[1]=true;
    for(int i=2;i<=10000000;i++)
    {
        if(isprime[i])
            continue;
        for(int j=i+i;j<=10000000;j+=i)
            isprime[j]=true;
    }
    ll a,b;
    cin>>a>>b;


    int cnt=0;
    for(int i=2;i<=10000000;i++){
        if(isprime[i])
            continue;
        ll now,next;
        now=1LL*i*i;
        while(1)
        {
            if(now>b)
                break;

            if(a<=now && now<=b)
                cnt++;
            next=1LL*i*now;
            if(next%now!=0)
                break;
            now=next;
        }
    }
    cout<<cnt;
    return 0;

}

hayman42 5년 전 0

혹시 next / now != i 가 안되는 이유를 어렴풋이라도 알려주실 수 있을까요?

저도 초보자라서 왜 안되는지는 잘 모르겠지만 % 가 되는 이유는 단순히 정말 절묘하게 next 가 오버플로우가 일어나면서 now 의 배수가 되는 데이터가 없기 때문 아닐까요?

kimsy96 5년 전 0

음.. 어렴풋이 이해했다고 생각했는데 아니었어요 여전히 모르겠네요 ㅋㅋㅋㅋ

저소스코드 돌려보면 40퍼센트 정도에서 틀렸다고 나오는데 반례도 못찾겠네요 음

kimsy96 5년 전 0

오버플로우가 발생해서 값이 음수로 튀니까 몫이 음수가 되어 저렇게 판별할 수 있을거라 생각했는데 ..

kimsy96 5년 전 0

몇몇 실력좋은 분들과 이야기 해본 결과

약간의 운이 작용했다..라는 결론을 얻었고

풀이는 참고만 하시고

오버플로우는 다른방식으로 처리하시길 권장합니다

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

문제

문제

출처

ICPC

1456번 질문

kimsy96 5년 전 0

kimsy96 5년 전 0

kimsy96 5년 전 0

kimsy96 5년 전 0

hayman42 5년 전 0

kimsy96 5년 전 0

kimsy96 5년 전 0

kimsy96 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말