Az 73318332000987272. Fibonacci szám tényleg "123456789"-cel kezdődik és végződik?

Alapötlet javítva, hogy keressünk egy gyorsabb algoritmust Google-lel:

[link]

Mivel itt is lehet minden műveletet moduló 10^9 csinálni, ezért szerintem ezzel meglesz.

Akkor lemaradtam… Gyakrabban kéne programoznom. Meg nem kellett volna leülnöm közben a TV elé…

Az én megvalósításom C-ben:

#include <stdio.h>

#define MOD 1000000000

#define LOG 64

#define SZAM 73318332000987272

typedef struct {

int a;

int b;

int c;

} matrix;

matrix szor(matrix x, matrix y)

{

long long a, b, c;

matrix z;

z.a = ((long long)x.a*(long long)y.a + (long long)x.b*(long long)y.b)%MOD;

z.b = ((long long)x.a*(long long)y.b + (long long)x.b*(long long)y.c)%MOD;

z.c = ((long long)x.b*(long long)y.b + (long long)x.c*(long long)y.c)%MOD;

return z;

}

matrix hatvany(matrix x, long long n)

{

matrix a[LOG], h;

int i;

a[0] = x;

for(i=0;i<LOG-1;i++) a[i+1] = szor(a[i], a[i]);

h.a = 1; h.c = 1; h.b = 0;

i = 0;

while(n)

{if(n%2) h = szor(h, a[i]);

n /= 2; i++;}

return h;

}

int main()

{

long long n=SZAM;

matrix e, k;

e.a = 1; e.b = 1; e.c = 0;

k = hatvany(e, n);

printf("%d\n%d\n%d\n",k.a,k.b,k.c);

return 0;

}

Az OUTPUT:

871709218

123456789

748252429

Process returned 0 (0x0) execution time : 0.024 s

Press any key to continue.

A második szám az Fn mod 10^9.