How can I solve this without using map method?

[salem c]

What have you managed to achieve so far?

And no, we're not in the business of entering competitions by proxy.

Oh, and now the OP has buggered off, the link to the original problem.
https://www.e-olymp.com/en/contests/13102/problems/124760

[Ganado]

Glad to see the topic is solved.

[dutch]

Now that the trash has been taken out, how would you solve this?
The constraints are pretty high.

Fibonacci numbers

As is known, the Fibonacci sequence is defined as:

F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) for all n > 1

Given the values of n and m, find the greatest common divisor of F(n) and F(m).

Input
Each line is a separate test case that contains two integers n and m (1 ≤ n, m ≤ 10^18).
The number of test cases does not exceed 1000.

Output
For each test case print in a separate line the value of GCD(F(n),F(m)),
taken by modulo 10^8.

Time limit 1 second
Memory limit 128 MiB

Input example #1
2 3
1 1
100 200

Output example #1
1
1
61915075

[deleted account xyzzy]

@Ganado, solved after the OP had a temper tantrum we wouldn't just do all the work for them.

I can't say I am sad to see 'em go, 'cuz I ain't.

[helios]

They probably want the closed-form expression of the sequence, but I don't think double would have enough precision to represent fib(10^18) exactly.

[dutch]

Standard double precision only has a range of about 308 decimal digits.
Standard (80-bit) long double has a range of about 4900 decimal digits.

#include <iostream>
#include <cmath>

int main()
{
    const long double s5 = sqrt(5.0L);
    int n = 23599; // highest before inf
    // Binet's Formula
    auto f = (1 / s5) * (std::pow((1 + s5) / 2, n) - std::pow((1 - s5) / 2, n));
    std::cout << f << '\n';
}

(Note that std:: is needed before the pows lest they default to returning a double.)

Interesting. This page seems to say that each new fib has a new prime factor (one that hasn't appeared in a previous fib's prime factorization).
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
The page shows the first 300 fibs factored, with the "new" primes in green. Prime indices are in red, and somehow for each of the prime indices the fib is all "new" primes. (A couple of fibs near the beginning don't follow the pattern.)

Edit: Now that I think about it, this is probably an artifact of only looking at the first 300.

[helios]

Standard double precision only has a range of about 308 decimal digits.
Standard (80-bit) long double has a range of about 4900 decimal digits.

That's only the size of the largest possible value. mantissa(2^exponent_size) * log10(2). double is only able to represent integers exactly up to about 2^53. between 2^53 and 2^54 only even values can be represented exactly, between 2^54 and 2^55 only multiples of 4, and so on.

(I had to think about this a lot when working in cryptocurrencies. double can represent exactly ever possible Bitcoin amount, but not every possible Ethereum amount.)

[dutch]

Yeah, I didn't say that right to just say they had that many digits. I meant that their exponent range is about ten to that power, so if you don't need the exact answer you could at least get an answer to 18 sig digs (not a big improvement on double's 15) and know it's magnitude. And the 80-bit long double is designed specifically to be able to hold a 64 bit integer (mantissa is 64 bits (I think with an explicit "ones" bit unlike regular double's implicit bit, but why?)).
https://en.wikipedia.org/wiki/Extended_precision#x86_extended_precision_format

[helios]

Man, what a blunder. I wrote "mantissa" instead of "exponent" earlier.

I meant that their exponent range is about ten to that power, so if you don't need the exact answer you could at least get an answer to 18 sig digs

Yeah, that's what I was getting at, before. It's not really clear whether they want the exact answer or not. The fact that they want the GCD modulo 1E+8 kind of suggests they do, but it's not really clear.

And the 80-bit long double is designed specifically to be able to hold a 64 bit integer (mantissa is 64 bits (I think with an explicit "ones" bit unlike regular double's implicit bit, but why?)).

Mmh... Good point. 2^64 is 19 decimal digits, so maybe that's what they had in mind. It's kind of lame to design a problem that will only run on some processors.

[lastchance]

#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;

using INT = unsigned long long;

const int M = 100000000;
const int Period = 150000000;


INT FibMod( INT n )
{
   n %= Period;

   INT a = 0, b = 1;
   if ( n == 0 ) return a;
   while( --n )
   {
      INT t = b;
      b += a;   if ( b >= M ) b -= M;
      a = t;
   }
   return b;
}


INT hFib( INT n, INT m )
{
   if ( n < m ) swap( m, n );

   if ( m == 1 ) return 1;
   if ( m == n ) return FibMod( n );
   return hFib( m, n - m );
}


int main()
{
   istringstream in( "7       \n"
                     "2 3     \n"
                     "1 1     \n"
                     "100 200 \n"
                     "6 9     \n"
                     "6 12    \n"
                     "6 15    \n"
                     "123456789012345 9876543210 \n" );

   INT n, m;
   int T;
   in >> T;
   while( T-- )
   {
      in >> n >> m;
      cout << n << '\t' << m << " ===> " << hFib( n, m ) << '\n';
   }
}

[helios]

Am I wrong, or did you do the opposite of what the problem asks for? The problem asks for GCD(fib(n), fib(m)) % 10^8, but it looks like you're calculating fib(GCD(n, m)) % 10^8. I don't think those are equivalent.

[lastchance]

helios wrote:

Am I wrong, or did you do the opposite of what the problem asks for? The problem asks for GCD(fib(n), fib(m)) % 10^8, but it looks like you're calculating fib(GCD(n, m)) % 10^8. I don't think those are equivalent.

No, I'm doing {GCD(fib(n), fib(m)) } % 10^8. The modulo 10⁸ is only done to one of the two possible exit points.

The reduction is done by INT hFib( INT n, INT m )
That is completely independent of M=10⁸. It has nothing directly to do with the HCF algorithm (which uses n%m, not n-m; look carefully).

hFib(n,m) is the function hcf( F(n), F(m) ), where F(n) is the nth Fibonacci number (with F(1)=F(2)=1).

There are only two exit points from the recursion in hFib():
m =1 (whence F(1)=1, so that's the highest common factor)
OR
n=m, in which case hcf(F(n),F(n))=F(n), so you are stuck with finding a large Fibonacci number, mod M. That is done by a different function int FibMod().


FWIW:
I see two main steps:
(1) Proving that hcf( F(n),F(m) ) = hcf( F(n-m),F(m) ), where m<n, without any modulo. This reduces the problem.
(2) Finding the value of a Fibonnaci number for very large n and then writing it modulo M.

Item (1) took me hours to prove myself, but I subsequently discovered it online in a different context.

Item (2) is fairly standard (i.e. I googled it). It turns out that Fibonacci numbers mod M have a period - the Pisano Period. I obtained that with a separate program by brute force. Luckily, here it is (relatively) small - it could have been anything between 3 and M², i.e. 10¹⁶. The latter would have crippled the method.


Well, that's my take on it. Somebody will have to get an account on the e-Olympiad site and try it out, I suppose. You'll need to change the output format if you want to put it in a competitive programming site.




The last three cases:

                     "6 9     \n"
                     "6 12    \n"
                     "6 15    \n"

should allow you (by writing out the first 15 Fibonacci numbers) to check the statement

hcf( F(n), F(m) ) = hcf( F(m), F(n-m) )

by hand. Dealing with the modulo is a different (and somewhat easier) problem.



As an example,

hcf(F(6),F(15)) = hcf(F(6),F(9)) = hcf(F(6),F(3)) = hcf(F(3),F(3)) = F(3) = 2

Check: F(6) = 8 and F(15) = 610; the highest common factor is 2.



Feel free to come up with a better alternative.

[dutch]

I was hoping lastchance might take a gander at this.
Nicely done!
That Period thing is pretty strange (where does 150 million come from?).
But hFib(n, m) == hFib(m, n - m) (where m <= n) is insane.
It brings the solution within reach.