BRUTEFORCE 질문요!

  • vi1409
    vi1409

    BRUTEFORCE

    저는 이 문제를 등비수열의 합으로 봤는데요
    초항이 start이고 N이 공비라고 두었습니다.
    값이 작을 때는 잘나오는거 같은데 커지면 문제가 발생합니다.
    MOD연산에서 문제가 발생하는 것 같은데
    만약 a/b(mod n) 일때 b하고 n이 서로소 이면 결과값이 상관 없는걸루
    알고있는데.. 아닌가요??

    #include<cstdio>
#define MOD 1000000007
long long power(long long a, long long b) {
    long long pow = 1;
    while (b){
        if (b & 1){
            pow = (pow * a)%MOD;
            --b;
        }
        a = (a*a)%MOD;
        b = b / 2;
    }
    return pow;
}
int main(){
    freopen("input.txt", "r", stdin);
    int t; scanf("%d", &t);
    while (t--){
        long long ans = 0, start, NpowerR;
        long long a, b, N, sub; scanf("%lld%lld%lld", &a, &b, &N);
        sub = b - a + 1;
        if (N == 1)
            printf("%lld\n", sub);
        else{
            start = power(N, a);
            NpowerR = power(N, sub);
            ans = ((start*((NpowerR - 1)) / (N - 1))) % MOD;
            printf("%lld\n", ans);
        }
    }
}

    10년 전
3개의 댓글이 있습니다.
  • Being
    Being

    정확히 무슨 말씀을 하시는지 모르겠으나 나머지를 취한 값들을 원소로 가지는 \mathbb{Z}_\textrm{MOD}에서 나눗셈 연산은 정의되지 않습니다.


    10년 전 link
  • vi1409
    vi1409

    감사합니다 ㅎ


    10년 전 link
  • Being
    Being

    물론 나눗셈과 비슷하게 생각할 수 있는, 곱셈의 역원은 경우에 따라 정의될 수 있습니다. :) 다만 그 사실을 활용하지 않아도 풀 수 있는 문제로 보이네요.


    10년 전 link

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