Note: I couldn't find exact terminology for this question. It is something like "Russian Peasant multiplication" for calculating exponent.

There's a well-known way of calculating $$$p^k$$$ as follow:

template<typename T> T pow(T p, int k) {
    T t = 1;
    while (k > 0) {
        if (k % 2 == 1) t = t * p;
        p = p * p;
        k /= 2;
    }
    return t;
}

We can reduce one multiplication ($$$1 * p$$$) from above implementation with a variable named first_mul:

template<typename T> T pow(T p, int k) {
    T t;
    bool first_mul = false;
    while (k > 0) {
        if (k % 2 == 1) {
            if (!first_mul) t = p, first_mul = true;
            else t = t * p;
        }
        p = p * p;
        k /= 2;
    }
    return t;
}

I found that when operator $$$*$$$ is very heavy, like matrix or polynomial multiplication, this trick reduces runtime a lot.

So I want to ask:
1. Is there a simple algorithm that is better than above algorithm for $$$k \leq 10^9, k \leq 10^{18}$$$, $$$k \leq 10^{100}$$$?
2. Is there any way to find the optimal number of multiplications in calculating $$$p^k$$$?

There are $$$N$$$ questions, each of them has $$$k$$$ options. For each question, only one option is correct. Giving a black box that returns the number of correct answers of a submission. You try to submit until getting $$$N$$$ correct answers (There is a strategy having at most $$$1 + (k-1) \times N$$$ submissions).

I have 3 questions:

1. What's the official name for this kind of problem? I couldn't find any paper mentioning the problem.

2. What's the best strategy to get all $$$N$$$ correct answers? How many submissions required in the worst case?

3. We can submit at most $$$L$$$ submissions, what's the highest expected number of correct answers can we achieve?

Hi all, I'm learning a very useful data struct int C++: set. I know set is a red-black tree so could we join two set into a new set with complexity O(log (number of elements)) in two set? And if we couldn't, what is the best algorithm to join two sets in C++? Thanks for helping.

Hi all, I just see some solutions of round #200 div 1 D . Seem that all solutions use "range query" data struct. Some use Segment tree like con_nha_ngheo's solution . But some others use like KADR's solution. This tree i saw in codeforces and topcoder . I don't know what it is and how it work. Could anyone help me explain it or show me some notes about it?

Hi everyone, I'm newbie to informatic and Codeforces. I have just finished my C++ class and now I am learning about algorithm. My teacher told that I should practice, practice and practice problems on some online judge webs but I feel tired. I'm just learning informatic 2 months and have no idea about algorithm. I always want to be a good algorithm programmer but I couldn't choose a effective method to learning it. Can anyone help me some way, learning algorithm before practice or practice then find algorithm compatible or another method? I'll very greatful for the help.