SPOJ.com - Problem BMS1988

BMS1988 - Fibonacci factorization

no tags

The Mysterious Affair at Byte Court

Hercule was quietly on hollydays (Noël) at Byte Court when Fibonacci and Lucas (well-dressed) knocked at his door.
They came in, and the first one said : "Monsieur, can you factorise my first 1001 terms, please?".
Hercule said : "It was useless to come in to ask that, but since you are here, I'll do that very quickly."
Then Lucas said : "It's not a speed challenge, we like Styles too, the shorter your code is, the best your score is."

Output

You have to output 1001 lines, the factorization of the 1001 first terms of the Fibonacci sequence.
See sample for output details.

Example

F(0)= 0
F(1)= 1
F(2)= 1
F(3)= 2
F(4)= 3
F(5)= 5
F(6)= 2^3
F(7)= 13
F(8)= 3 * 7
F(9)= 2 * 17
F(10)= 5 * 11
F(11)= 89
F(12)= 2^4 * 3^2
[...]
F(1000)= 3 * 5^3 * 7 * 11 [...]

Submit solution!

hide comments

< Previous 1 2 Next >

	mehmetin: 2020-02-09 16:14:57 Do we need an advanced factorization algorithm like "quadratic sieve" to solve this problem? =(Francky)=> No, a scholar method is enough here to get AC. But to get high score, you need to solve the riddle part... Good luck. Last edit: 2020-02-09 17:11:00
	Alessandro Amici: 2018-03-11 15:44:17 Yessss!! 360 characters! I wrote this solution three years ago but it was getting TLE by a tiny fraction of a second. Now with new hardware or with the new interpreter it gets AC. I don't even know what it does anymore :D :D :D =(Francky)=> Congrats, and the game is not over ! =(alexamici)=> Yup! One more big insight and we are at 314. This is truly never ending! Last edit: 2018-03-12 22:39:57
	knowcode: 2015-07-26 17:39:15 is it okay if giving output of factors F(0) and F(1) are not a part of factorization algorithm? =(Francky)=> You must output these as in the sample ; no other choice ; there's no factorization here. Did I answer your question ? I'm not sure ! Last edit: 2015-07-26 22:16:51
	Alessandro Amici: 2015-01-11 15:28:19 Francky, this is one of the problems I enjoyed the most in SPOJ on so many levels, second only to SIZECON. Compliments and thank you! --(Francky)--> Many thanks for your appreciation, congrats for your achievements. You're welcome. Last edit: 2015-01-11 15:41:45
	Alessandro Amici: 2015-01-03 13:08:44 Got it :) Now let's golf. --francky--> Congrats, now I hope you'll enjoy this new part too ;-) --alexamici-->Aha! 415! Last edit: 2015-01-10 18:39:35
	Alessandro Amici: 2015-01-03 11:24:00 @Francky great problem! Can you please check my submissions 13335447 and 13335452? I can get AC in the second one by putting a lot of precomputed values, but I don't understand how the first one is getting NZEC. In order not to give up any spoiler I put my specific questions in comments inside the submissions. Thanks! --Francky--> Congrats for the big part you've yet achieved. For the first one, [...] Last edit: 2015-01-03 13:20:15
	ruslion: 2013-01-30 03:09:53 if I factorize every sequence member as F(n) = a(n) * b(n) will the answer be accepted? Or I should represent it as F(n) = 2^a(n) * 3^b(n) * 5^c(n).....etc. --ans--> see sample for output details : "F(12)= 2^4 * 3^2" is the only format for answer to get AC. Last edit: 2013-01-30 07:01:06
	Francky: 2013-01-23 15:57:37 @pinco : we can't neither read psetter files, it would too easy to solve any problem. The problem code is BMS1988, it's not for nothing !!! stdin can't be anything else than that it is to make a good challenge.
	Francky: 2013-01-22 10:02:29 Spoil : within a spoj submission, it's impossible to download the solution from Internet at http://mersennus.net/fibonacci/, but Hercule is a stdin detective... Everybody can solve the task without being a detective, and it's recommended to do so at first attempts. Enjoy ;-) For your information judge is classic-spoj-source-lenght. The Mysterious Affair at Styles is an almost 100 years old Agatha Cristie's novel, introducing for the first time Hercule Poirot. Last edit: 2013-01-22 10:18:44
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-21 20:17:04 Uwah... only ~760 bytes to solve this problem :-O

Submit solution!

Added by:	Francky
Date:	2013-01-20
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem