BRUTEFORCE 공식 질문입니다.

  • skylife927
    skylife927

    문제 링크
    https://algospot.com/judge/problem/read/BRUTEFORCE

    등비수열의 합 공식을 이용하여 아래와 같이 구했습니다.
    Sn = r(r^n-1) / (r-1); 을 이용하여

    1부터 B까지의 Sb
    1부터 A-1까지의 Sa

    Sb-Sa를 하였는데, N의 값이 커지는 경우에는 오류가 납니다.

    어디서 문제를 캐치 하지 못했는지 조언 부탁드립니다.

    답변 미리 감사합니다.!

    #include <iostream>

#define DIVIDE 1000000007

using namespace std;

long long A;
long long B;
long long N;
long long Sb;
long long Sa;
int main(int argc, char** argv)
{
    int test_case;
    int T;

    cin >> T;
    for(test_case = 0; test_case < T; test_case++)
    {
        cin>>A>>B>>N;
        Sb = 1;
        Sa = 1;
        if(N == 1){
            cout<<B-A+1<<endl;
        }
        else{
            //B의 가지수에서 A-1 가지수를 빼면된다.
            for(int i=1; i<=B; i++){
                Sb = (Sb * N) % DIVIDE;
                if(i==A-1){
                    Sa = Sb;
                }
            }

            Sb = (N * (Sb - 1)) / (N-1);
            Sb = Sb % DIVIDE;

            Sa = (N * (Sa - 1)) / (N-1);
            Sa = Sa % DIVIDE;

            cout<<Sb - Sa<<endl;
        }
    }
    return 0;
}

    8년 전
2개의 댓글이 있습니다.
  • SinAska
    SinAska

    저도 이문제에 같은 문제를 겪어서, 고쳐야될 부분 몇가지를 알려드릴수 있을 것 같네요.
    1. 등비수열의 합공식
    이 문제에서 Sb, Sa는 아래와 같은 항들로 구성됩니다.
    S = r+r^2+r^3+ ....+r^B
    rS = r^2+r^3+...r^(B+1)
    S = (r^(B+1)-r)/(r-1)
    위 식을 토대로보면, B항의 경우 B+1까지 계산해주셔야되고, A항의 경우 A까지 계산해주셔야합니다.
    2. 문제는 거의 다푸셨는데, 오답이 크게 나오는 이유는 MOD연산에 대한 역원 계산을 포함하지 않았기때문입니다.
    뺄셈에 대한 MOD : (A-B)%MOD = (A%MOD - B%MOD + MOD)%MOD
    나눗셈에 대한 MOD : (A/B)%MOD = (A%MOD)*(B^(MOD-2))%MOD (MOD가, 소수일때만 성립)
    3. 성능과 관련된 건, A가 최대 1억이 될수있고, 테스트케이스가 50개라는 걸 감안해보면
    N시간 POW함수로는 시간초과에 위험이 있습니다.
    POW연산은 log(n)시간에 가능합니다. 이는 찾아보시면, 쉽게 자료를 구하실 수 있을꺼에요.


    8년 전 link
  • skylife927
    skylife927

    감사합니다!! 새벽한시에 올려주시다니 ㅎㅎ 감사합니다. ㅋ


    8년 전 link

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