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;
    }
    

    2년 전
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)시간에 가능합니다. 이는 찾아보시면, 쉽게 자료를 구하실 수 있을꺼에요.


    2년 전 link
  • skylife927
    skylife927

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


    2년 전 link
  • 댓글을 남기시려면 로그인하세요.