Problem:

You're given the following sequence:

Write an algorithm with complexity O( log(n) ) to get the value of S.

Solutions:

1) the naive algorithm with a complexity O(n)

#include <iostream>

using namespace std;

int main() {
    // read the value of "a" and "n".. 
    long long a, S, A; 
    int n, i; 
    cin >> a >> n;
    int fct = 1; 
    S = 0, A = a; 
    for(i = 0; i < n; i++) {
        S += (fct * A); 
        A *= a, ++fct; 
    }
    cout << S << "\n";  
}

2) faster algorithm with time complexity O(log(n)):

we can get the value of S using the following formula:

here's the code:

#include <iostream>

using namespace std;

long long power(long long a, int p) { //this function complexity is O(log(n)) 
    long long res = 1; 
    while(p) {
        if(p & 1) 
            res *= a; 
        a *= a; 
        p >>= 1; 
    }
    return res; 
}
int main() {
    // read the value of "a" and "n".. 
    long long a, S, An, An1; 
    int n; 
    cin >> a >> n;
    if(a == 1) 
        S = (n * (n + 1)) >> 1; 
    else {
        An = power(a, n); // value of a^n 
        An1 = An * a; // value of a^(n + 1)

        S = (((a * (1 - An)) / (1 - a)) - n * An1) / (1 - a); 
    }
    cout << S << "\n"; 
}

here's the proof of the above formula:

This problem is an exercise in Competitive programming book Edition 3, page [193].