Constraining the least greatest and the greatest least
This problem is a relatively easy one. We are given some numbers like 1e6, 1e12 and 1e18. 1e18 ruled out the possibility of any sort of brute force. 1e12 means that we need to do some optimization on the numbers from 1e6 to 1e12 since it is still a burden for computer. Well, 1e6 is not so big a number, we can do whatever we like.
After sometime's thought, I found that there is a neat formula for this problem(it is not difficult to derive the formula). With this formula, it is very easy to find the number of valid lists for certain gcd and lcm.(Well, after I read the discussion, I found that this formula may be derived after a moment's thought!) My code first ran for 5 seconds, then I did some optimization since 1e18 is too large in some sense, then the code runs for 0.18 second.
Friday, September 20, 2013
Sunday, September 8, 2013
project euler problem 265
Binary Circles
This is a very simple problem. A simple recursive function can get the correct answer. It only needs 50 ms to get the correct answer.
This is a very simple problem. A simple recursive function can get the correct answer. It only needs 50 ms to get the correct answer.
project euler problem 435
Polynomials of Fibonacci numbers
This problem is relatively simple. But a little bit math is required to avoid computer to do huge amount of work. This problem is very similar to some older problem. You may first ask yourself a simpler question, how to calculate the 10^15th Fibonacci number(mod n)?
After I get the answer for F_7(11) correct. I immediately get the correct solution for the problem. The only bad thing is that I used some sort of bigInteger in my code, but it may not be necessary if you handle the problem in a different approach.
This problem is relatively simple. But a little bit math is required to avoid computer to do huge amount of work. This problem is very similar to some older problem. You may first ask yourself a simpler question, how to calculate the 10^15th Fibonacci number(mod n)?
After I get the answer for F_7(11) correct. I immediately get the correct solution for the problem. The only bad thing is that I used some sort of bigInteger in my code, but it may not be necessary if you handle the problem in a different approach.
Saturday, September 7, 2013
project euler problem 266
Pseudo Square Root
This problem is not easy in my opinion. I forgot how I solved the problem for the first time. But I remembered that it was slow. I then read the discussion and found a clever solution for this problem. I was surprised that many people knew the algorithm or found the algorithm by themselves.
The algorithm can be used to solve problem 185 or problem 418 and now problem 461.
This problem is not easy in my opinion. I forgot how I solved the problem for the first time. But I remembered that it was slow. I then read the discussion and found a clever solution for this problem. I was surprised that many people knew the algorithm or found the algorithm by themselves.
The algorithm can be used to solve problem 185 or problem 418 and now problem 461.
Subscribe to:
Posts (Atom)