#include <iostream> #include <vector> #include <string> #define ull unsigned long long using namespace std; ull pomnoz(ull x, ull y, ull MOD) { ull wynik = 0, temp, trzy = 3; while(y > 0) { temp = trzy & y; wynik += temp * x; x <<= 2; x %= MOD; y >>= 2; wynik %= MOD; } return wynik; } struct macierz { ull a, b, c, d; ull MOD; // a b // c d macierz& operator*=(macierz &temp) { ull a1 = ( pomnoz(temp.a, a, MOD) + pomnoz(temp.c, b, MOD) )%MOD, b1 = ( pomnoz(temp.b, a, MOD) + pomnoz(temp.d, b, MOD) )%MOD, c1 = ( pomnoz(temp.a, c, MOD) + pomnoz(temp.c, d, MOD) )%MOD, d1 = ( pomnoz(temp.b, c, MOD) + pomnoz(temp.d, d, MOD) )%MOD; a = a1; b = b1; c = c1; d = d1; return *this; } macierz(ull a1, ull b1, ull c1, ull d1, ull MOD1) { a = a1; b = b1; c = c1; d = d1; MOD = MOD1; } void wypisz() { cout << a << " " << b << endl << c << " " << d << endl; } macierz potega(ull pot) // nie dziala dla 0!! { macierz wynik(1, 0, 0, 1, MOD), temp = (*this); while(pot > 0) { if (pot & 1) wynik *= temp; temp *= temp; pot /= 2; } return wynik; } }; ull liczba(string s) { ull wynik = 0; for(int i = 0; i < s.size(); i++) wynik = 10* wynik + s[i] - '0'; return wynik; } ull pom[21] = {1, 60, 5, 5, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}, pomwyk = 1; vector < vector < pair < ull, macierz > > > V; int main() { string s; cin>>s; V.clear(); // a k = 0? V.resize(30); for(int i=0; i<30; i++) V[0].clear(); ull MOD = 1; for(int i=0; i<s.size(); i++) MOD *= 10; ull n = liczba(s); V[0].push_back({0, macierz(1, 1, 1, 0, MOD)}); macierz mnoznik(1, 1, 1, 0, MOD); ull temp = 10; for(int i=1; temp <= MOD; i++) { for(int j=0; j < V[i-1].size(); j++) { macierz M = V[i-1][j].second; ull par = V[i-1][j].first; for(int k = 0; k < pom[i]; k++) { if (M.d % temp == n % temp) { V[i].push_back({par, M}); } par += pomwyk; M *= mnoznik; } } pomwyk *= pom[i]; mnoznik = mnoznik.potega(pom[i]); temp *= 10ULL; } if (V[s.size()].size() == 0 || (V[s.size()][0].first == 0 && V[s.size()].size() == 1)) printf("NIE\n"); else { if (V[s.size()][0].first != 0) printf("%llu", V[s.size()][0].first); else printf("%llu", V[s.size()][1].first); } /*macierz M(1, 1, 1, 0, 1000000000000000000LL); 22 M = M.potega(1500000000000000001LL); M. wypisz(); */ return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #include <iostream> #include <vector> #include <string> #define ull unsigned long long using namespace std; ull pomnoz(ull x, ull y, ull MOD) { ull wynik = 0, temp, trzy = 3; while(y > 0) { temp = trzy & y; wynik += temp * x; x <<= 2; x %= MOD; y >>= 2; wynik %= MOD; } return wynik; } struct macierz { ull a, b, c, d; ull MOD; // a b // c d macierz& operator*=(macierz &temp) { ull a1 = ( pomnoz(temp.a, a, MOD) + pomnoz(temp.c, b, MOD) )%MOD, b1 = ( pomnoz(temp.b, a, MOD) + pomnoz(temp.d, b, MOD) )%MOD, c1 = ( pomnoz(temp.a, c, MOD) + pomnoz(temp.c, d, MOD) )%MOD, d1 = ( pomnoz(temp.b, c, MOD) + pomnoz(temp.d, d, MOD) )%MOD; a = a1; b = b1; c = c1; d = d1; return *this; } macierz(ull a1, ull b1, ull c1, ull d1, ull MOD1) { a = a1; b = b1; c = c1; d = d1; MOD = MOD1; } void wypisz() { cout << a << " " << b << endl << c << " " << d << endl; } macierz potega(ull pot) // nie dziala dla 0!! { macierz wynik(1, 0, 0, 1, MOD), temp = (*this); while(pot > 0) { if (pot & 1) wynik *= temp; temp *= temp; pot /= 2; } return wynik; } }; ull liczba(string s) { ull wynik = 0; for(int i = 0; i < s.size(); i++) wynik = 10* wynik + s[i] - '0'; return wynik; } ull pom[21] = {1, 60, 5, 5, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}, pomwyk = 1; vector < vector < pair < ull, macierz > > > V; int main() { string s; cin>>s; V.clear(); // a k = 0? V.resize(30); for(int i=0; i<30; i++) V[0].clear(); ull MOD = 1; for(int i=0; i<s.size(); i++) MOD *= 10; ull n = liczba(s); V[0].push_back({0, macierz(1, 1, 1, 0, MOD)}); macierz mnoznik(1, 1, 1, 0, MOD); ull temp = 10; for(int i=1; temp <= MOD; i++) { for(int j=0; j < V[i-1].size(); j++) { macierz M = V[i-1][j].second; ull par = V[i-1][j].first; for(int k = 0; k < pom[i]; k++) { if (M.d % temp == n % temp) { V[i].push_back({par, M}); } par += pomwyk; M *= mnoznik; } } pomwyk *= pom[i]; mnoznik = mnoznik.potega(pom[i]); temp *= 10ULL; } if (V[s.size()].size() == 0 || (V[s.size()][0].first == 0 && V[s.size()].size() == 1)) printf("NIE\n"); else { if (V[s.size()][0].first != 0) printf("%llu", V[s.size()][0].first); else printf("%llu", V[s.size()][1].first); } /*macierz M(1, 1, 1, 0, 1000000000000000000LL); 22 M = M.potega(1500000000000000001LL); M. wypisz(); */ return 0; } |