BRUTEFORCE

알고스팟 BRUTEFORCE

배울점

1. 26번째 줄에 나누기 연산이 포함된 MOD연산을 처리 하는 법.
2. 등비수열의 합 공식을 반복문을 통해 수행시간이 n이 아닌 logn으로 처리하는 법

[-] Collapse

#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(){
    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)%MOD * power(N-1, MOD-2))) % MOD;
            printf("%lld\n", ans);
        }
    }
}