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 `#include #include #include #include using namespace std; typedef long long LL; namespace mul { LL mul(LL a, LL b, LL mod) { LL res = 0; while (a) { if (a % 2) { res = res + b; if (res >= mod) res -= mod; } a /= 2; b = b + b; if (b >= mod) b -= mod; } return res; } }; #define PB push_back LL MOD; struct Fmatrix { LL m[2][2]; Fmatrix() { m[0][0] = m[0][1] = m[1][0] = 1; m[1][1] = 0; } }; Fmatrix operator*(const Fmatrix &lhs, const Fmatrix &rhs) { Fmatrix res; res.m[0][0] = res.m[0][1] = res.m[1][0] = res.m[1][1] = 0; for (int i=0;i<2;i++) for (int j=0;j<2;j++) for (int k=0;k<2;k++) res.m[i][j] = (res.m[i][j] + mul::mul(lhs.m[i][k], rhs.m[k][j], MOD)) % MOD; return res; } LL fib(LL n, LL mod) { MOD = mod; if (n < 2) return n; n -= 2; Fmatrix res = Fmatrix(); Fmatrix sq = Fmatrix(); for (;n;n/=2) { if (n % 2) res = res * sq; sq = sq * sq; } return res.m[0][0]; } LL period[20]; LL solve(LL n, int len) { vector cand, new_cand; LL mod = 10; for (int i=0;i<60;i++) if (fib(i, 10) == n % 10LL) cand.PB(i); for (int i=1;i