Jak obliczyć fib(n)^2 mod 1000000007?
Tu jest program który (wg. mnie) to wykonuje: https://ideone.com/cuGkK
Jednak wyniki nie są do końca poprawne.
PS. n<(2^31)-1
0
0
x.c=power_modulo_fast(x.c); a po co to? czemu nie
x.d * x.d % mod?
PARI/GP (polecam swoją drogą)
gp > lift(Mod([0,1;1,1],1000000007)^2423)
[70703389 976466852]
[976466852 47170234]
Twój program bez n+=2; oraz bez x.c=power.....
wejście:
2423
wyjście:
70703389 976466852 976466852 47170234
0
x.c=power_modulo_fast(x.c); a po co to? czemu nie
x.d * x.d % mod?
x.c * x.c % mod - wydaje mi się, że przekroczy to zakresy. Obliczenia będą wykonywane po kolei, a więc najpierw wymnoży x.c*x.c. Jeśli x.c np. będzie równe 976395637, to podniesienie tego do kwadratu zdaje się, że zostanie błędnie wykonane, nawet jeśli później jest %mod. Dlatego musiałem zastosować potęgowanie modularne.
Problem jest (tak mi się wydaje w tym), że funkcja matrix power(matrix x, int n) zwraca fib(n) % m. Natomiast ja następnie podnoszę to do kwadratu. A powinienem najpierw do kwadratu podnieść fib(n), a dopiero później zastosować %m.
Bo czy to jest prawdziwe? (aa) %m = ((a % m)(a % m)) % m.
Twój program bez n+=2; oraz bez x.c=power.....
wejście:
2423
wyjście:
70703389 976466852 976466852 47170234
n+=2 - muszę to zostawić (to jest mi potrzebne do rozwiązania zadania)
Nie wiem skąd pojawiły Ci się takie wyjścia.
Skróciłem nieco kod: http://ideone.com/pu2Hd
0
x.x jest typu long long, skoro mniejsze od 2^32-1 to można bezpiecznie podnosić do kwadratu
(aa) %m == ((a % m)(a % m)) % m (z definicji)
i korzystasz z tego w power_modulo_fast()
printf("%lld %lld %lld %lld\n", x.a, x.b, x.c, x.d)
0
x.x jest typu long long, skoro mniejsze od 2^32-1 to można bezpiecznie podnosić do kwadratu
Faktycznie, masz racje.
(aa) %m == ((a % m)(a % m)) % m (z definicji)
i korzystasz z tego w power_modulo_fast()
Sam się teraz zastanawiam dlaczego w to zwątpiłem i sobie przypominam..
Ponieważ (x.cx.c)%1000000007 oraz power_modulo_fast(x.c) zwracają różne wyniki... Nie do końca rozumiem dlaczego.
Np. n=200.
Wersja z użyciem (x.cx.c)%1000000007, wynik:450435314
Wersja z użyciem power_modulo_fast(x.c), wynik: 41418325
0
gp > a=Mod([1,1;1,0],1000000007)^(200+2)
[Mod(407981060, 1000000007) Mod(878671356, 1000000007)]
[Mod(878671356, 1000000007) Mod(529309711, 1000000007)]
gp > a[1,2]^2
Mod(450435314, 1000000007)
zamiast
for (i=1; i<=b; i<<=1)
powinno być
for ( ; b ; b>>=1 )
a wiesz, że łatwo to przerobić tak by dobrze działało dla long long n, mod;
0
Więc jeśli dobrze zrozumiałem, to to już powinno być poprawne, tak?
http://ideone.com/1rfkB
0
gp > Mod(fibonacci(5+2),1000000007)^2
Mod(169, 1000000007)
0
gp > Mod(fibonacci(5+2),1000000007)^2
Mod(169, 1000000007)
Nie do końca rozumiem co chciałeś mi przez to przekazać.
(((fib(5+2) mod 1000000007)^2) mod 1000000007) = 169
OK, moj program tez tak zwraca..
0
i właśnie to chciałem pokazać