Divisibility 문제 질문드립니다.

  • 최병희
    최병희

    저는 map에다가 값을 다 집어넣고 시작했거든요.
    str은 입력받은 문자열이구요.
    size는 문자열의 길이입니다.

    for(i = 0; i < str.size(); ++i)
{
            size--;
            map::iterator p = index.find(str[i]); 
            if(size == 0)
                        ans += (long long)(*p).second;
            else
                        ans += (long long)(*p).second * (long long)pow(62, (double)size);
}

    이렇게 해서 ans % 61 로 해서 yes, no를 출력했는데요.

    sample input은 제대로 나오는데요. WA가 뜨네요 ㅠㅠ

    뭐가 잘못된 걸까요?... 허접이라 힘드네요


    13년 전
2개의 댓글이 있습니다.
  • VOCList
    VOCList
    1. 문자열의 길이가 1만까지 들어올 수 있는데, 만약에 1만길이의 문자열이 들어온다면 ans에는 62^10000 을 넘는 수가 들어가려고 할 수 있습니다. ans가 long long형이라고 해도 오버플로우가 충분히 날 수 있는 숫자가 되지용.
    2. double을 이용해서 pow를 하셨는데, 잘 아시겠지만 부동소수점 표기법은 표현해야 할 숫자가 길어지다보면 표현을 다 하지 못하고 버려버리는 부분이 생겨 실제 수와 오차가 생기게 됩니다ㅣ. 62^10000쯤 되는 수라면 double형으로도 오차없이 모든 수를 기록하고 있기는 힘들거에요. => 오버플로우와 오차 문제를 해결하신다면 유혈사태는 이하생략...

    13년 전 link
  • astein
    astein
    1. 하나 덧붙이면 double의 범위는 1.7E +/- 308 (15 digits) 입니다. 그런데 62^10000 이면 대략 18000자리?의 수가 되어 double의 범위를 벗어납니당.

    13년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.