등비 수열의 합

1이 초항 공비가 base인 등비 수열의 up번째 까지의 합
신기하네 ㅎㅎ
관련 문제 : 알고 스팟 BRUTEFORCE
[-] Collapse

long long powmodsum(long long base, long long up) {
    long long res = 0;
    long long mul = 1;
    while (up){
        if (up % 2){
            res = (res*base + mul) % mod;
        }
        mul = (mul * base + mul) % mod;
        base = base * base % mod;
        up >>= 1;
    }
    return res;
}

////////////////////////////////////////////////////////////////////
ans를 구하는 과정을 보면 등비수열의 합 공식은 a*(r^n-1)/(r-1)인데
연산 중 오버플로가 발생하지 않는다면 상관없는데 오버플로가 발생할 경우
문제가 된다 그래서 추가로 (a*(r^n-1)/(r-1))%MOD MOD를 붙이는데
이게 항상 성립되지가 않는다. 따라서 항상 성립되게 하려면
(a*(r^n - 1)/(r-1))%MOD = (a*(r^n - 1)*(r-1)^(MOD-2))%MOD 이다.
즉, 나눠야 하는 값 대신 (r-1)^(MOD-2)를 곱해주는 것이다.

[-] 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);
        }
    }
}