Problem 145 What kind of an algorithm should we use
Back to Problem Solutions forum
During the process of research, I find many approaches that do not work to solve this problem. For instance, I tried to use Euler's method, Fermat's Little Theorem or some other techniques to find a solution. (It seems like they work large numbers, and they do but not for this problem)
I spend nearly a day just doing the research. I am not saying that doing research is bad. However, since there are many approaches to this problem and only couple of them works. Finally, I applied an algorithm that writes on the Wikipedia page and it worked.
I would suggest that creating a page for an algorithm or showing a related wiki page can help the participants.
Hello!
First of all, let me heartily congratulate you on successfully finding the right algorithm :)
I would suggest that creating a page for an algorithm or showing a related wiki page can help the participants.
That is subtle issue. You may see that problem statement gives vague hints, but really it doesn't say directly "use binary exponentiation and take modulos at each step" :)
So with these "advanced" problems it is intended that some research is made, as you said... So I'm hesitant about giving direct link or explanation...
However from now participants may easily found our discussion in the forum and get a hint above, ha-ha - probably it is enough :)
Interesting point is that you've said:
I tried to use Euler's method, Fermat's Little Theorem
Honestly, I think on general "binary exponentiation" method is not a great secret, and far less "advanced" compared to things you've mentioned. I guess your background is much deeper in math (than mine, for example) and this diverted you initially :)
The approach is also much older than these: I think ancient babylonyans used its modified version (binary multiplication) to multiply numbers (they can't use multiplication table in their numeral system with base 60).
The trouble for me was that I couldn't create problem on simply calculating problem about "raising A to power B", as most python users will simply use built-in operation. At the same time the algorithm deserves to be known...
Hey!
However from now participants may easily found our discussion in the forum and get a hint above, ha-ha - probably it is enough :)
Yes, I think so. However, if you want to you can remove the question.
Honestly, I think on general "binary exponentiation" method is not a great secret and far less "advanced" compared to things you've mentioned. I guess your background is much deeper in math (than mine, for example) and this diverted you initially :)
I was searching about the algorithms online and I came across these two things, Euler's and Fermat's Theorem.
I tried to use them however for large numbers such as billions or hundred million they do not work well. My math is not so good... I don't have much knowledge about the algorithms and that's kind of a problem...
The trouble for me was that I couldn't create a problem on simply calculating problem about "raising A to power B", as most python users will simply use built-in operation. At the same time, the algorithm deserves to be known...
Indeed you are right. That would be also so simple. The algorithm is nice actually. I am using python, however, I don't know any built-in functions that can calculate this type of large powers.
So with these "advanced" problems it is intended that some research is made, as you said... So I'm hesitant about giving direct link or explanation...
That's totally fine. I can understand
Thank you