jankowalski25 |
» 2017-11-02 18:16:28 if( wynik > m ) wynik -= m;
|
mateczek: Większe lub równe. Widzę, że garlonicon też popełnił ten błąd. Przecież m % m == 0 . |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-11-03 17:06:09 Użyłem własnych macierzy, ale nie wiem jak przekonwertować je na inta. #include <iostream>
using namespace std;
struct Matrix_2x2 {
int a, b, c, d;
Matrix_2x2() { }
Matrix_2x2( int a1, int b1, int c1, int d1 ) {
a = a1;
b = b1;
c = c1;
d = d1;
}
};
Matrix_2x2 operator *( Matrix_2x2 A, Matrix_2x2 B ) {
return Matrix_2x2(
A.a * B.a + A.b * B.c, A.a * B.b + A.b * B.d,
A.c * B.a + A.d * B.c, A.c * B.b + A.d * B.d
);
}
ostream & operator <<( ostream & out, Matrix_2x2 mat ) {
return out <<
mat.a << ' ' << mat.b << '\n' <<
mat.c << ' ' << mat.d << '\n';
}
int power_modulo_fast( int a, int b, int m )
{
int i;
int result = 1;
long int x = a % m;
for( i = 1; i <= b; i <<= 1 )
{
x %= m;
if(( b & i ) != 0 )
{
result *= x;
result %= m;
}
x *= x;
}
return result;
}
int main() {
Matrix_2x2 m = Matrix_2x2( 1, 1,
1, 0 );
int t, a, n;
int wynik;
Matrix_2x2 mac = m;
cin >> t;
while( t-- )
{
cin >> a >> n;
if(( a == 1 ) ||( a == 2 ) ) cout << 1 % n;
else
{
int wynik = power_modulo_fast( m, a, n );
cout << wynik;
}
}
return 0;
}
|
|
mateczek |
» 2017-11-03 19:07:58 | ale nie wiem jak przekonwertować je na inta |
a co chcesz zrobić z tymi macierzami?? (do czego chcesz je użyć??). jak chcesz je "przekonwertować" na inta?? (to są dwie różne rzeczy macierz i int) :P bez kitu ale nie widzę w tym żadnego sensu |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-11-03 19:23:22 Mam zamiar obliczyć entą liczbę w ciągu fibonacciego za pomocą szykiego potęgowania modularnego macierzy i obliczyc modulo tej liczby. Funkcja szybkiego potęgowania działa na intach przez co nie mogę przekazać do niej zmiennej Matrix_2x2 o nazwie m. |
|
mateczek |
» 2017-11-03 19:42:02 skoro to ma być funkcja szybkiego potęgowania macierzy to musisz znaleźć, lub napisać funkcję która działa na macierzach. (ta działająca na intach się nie nada) |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-11-03 19:56:55 Wymyśliłem coś takiego. To narazie wersja bez modulo, bo nie wiem czy wcisnąć je gdzieś w tą funkcje czy dopiero na końcu przy wypisywaniu. template < typename M >
M pot_szybkie( M a, unsigned int n )
{
if( n % 2 == 1 ) return a * pot_szybkie( a, n - 1 );
else return( pot_szybkie( a, n / 2 ) * pot_szybkie( a, n / 2 ) );
}
|
|
mateczek |
» 2017-11-03 20:30:15 zdecydowanie wcisnąć. nie policzysz liczby większej niż fib(94) na standardowych typach danych w unsigned long long zmieści się max fib(94) |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-11-03 21:35:32 Znalazłem w internecie własność dla potęgowania modualrnych: A^B mod C = ( (A mod C)^B ) mod C. Lecz w tym kodzie coś nie gra... template < typename M >
M pot_szybkie( M a, unsigned int n )
{
if( n % 2 == 1 ) return a * pot_szybkie( a, n - 1 );
else return( pot_szybkie( a, n / 2 ) * pot_szybkie( a, n / 2 ) );
}
int main() {
Matrix_2x2 m = Matrix_2x2( 1, 1,
1, 0 );
int t, a, mod;
int wynik;
cin >> t;
while( t-- )
{
cin >> a >> mod;
if(( a == 1 ) ||( a == 2 ) ) cout << 1 % mod;
else
{
cout << pot_szybkie(( m % mod ), a ) % mod;
}
}
return 0;
}
|
|
| 1 2 3 4 « 5 » 6 7 |