#include "stdio.h" #include <map> long long cykl[20]; long long offsetCnt[20]; long long offset[20][50000]; std::map<long long, long long> Fmap; long long sqrMod(long long a) { long long a1 = a / 1000000000; long long a0 = a % 1000000000; long long res = (((2 * a1 * a0) % 1000000000LL) * 1000000000LL + a0 * a0) % (1000000000LL*1000000000LL); return res; } long long FIB(long long n) { if (n == 0) { return 0; } if (n == 1) { return 1; } if (n == 2) { return 1; } std::map<long long, long long>::iterator it = Fmap.find(n); if (it != Fmap.end()) { return it->second; } if ((n & 1) == 1) { long long f1 = FIB((n + 1) / 2); long long f2 = FIB((n - 1) / 2); long long res = (sqrMod(f1) + sqrMod(f2)) % (1000000000LL*1000000000LL); Fmap[n] = res; return res; } else { long long f1 = FIB((n / 2) + 1); long long f2 = FIB((n / 2) - 1); long long res = (sqrMod(f1) - sqrMod(f2) + (1000000000LL*1000000000LL)) % (1000000000LL*1000000000LL); Fmap[n] = res; return res; } } int main() { char str[100]; scanf("%s", str); int dig = 0; while (str[dig] != 0) { dig++; } // printf("FIB:%lld\n", FIB(45LL)); /* for (int i = 0; i < 1000; i++) { printf("%i:%lld\n", i, FIB(i)); } */ cykl[0] = 1; offsetCnt[0] = 1; offset[0][0] = 0; long long mask = 1; int d = 1; while (d <= dig) { mask *= 10; long long i = cykl[d - 1]; while ((FIB(i) % mask) != 0 || (FIB(i + 1) % mask) != 1) { i += cykl[d - 1]; } cykl[d] = i; //printf("CYKL:%i %lld\n", d, cykl[d]); d++; } mask = 1; d = 1; long long val = 0; while (d <= dig) { offsetCnt[d] = 0; val += mask * (str[dig - d] - '0'); mask *= 10; long long p = 0; while (p < cykl[d]) { for (int i = 0; i < offsetCnt[d - 1]; i++) { if ((FIB(p + offset[d - 1][i]) % mask) == val) { offset[d][offsetCnt[d]] = p + offset[d - 1][i]; offsetCnt[d]++; } } p += cykl[d - 1]; } d++; } if (offsetCnt[dig] > 0) { printf("%lld\n", offset[dig][offsetCnt[dig] - 1]); //printf("%s %lld -> %lld\n", str, offset[dig][offsetCnt[dig] - 1], FIB(offset[dig][offsetCnt[dig] - 1])); } else { printf("NIE\n"); } 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 "stdio.h" #include <map> long long cykl[20]; long long offsetCnt[20]; long long offset[20][50000]; std::map<long long, long long> Fmap; long long sqrMod(long long a) { long long a1 = a / 1000000000; long long a0 = a % 1000000000; long long res = (((2 * a1 * a0) % 1000000000LL) * 1000000000LL + a0 * a0) % (1000000000LL*1000000000LL); return res; } long long FIB(long long n) { if (n == 0) { return 0; } if (n == 1) { return 1; } if (n == 2) { return 1; } std::map<long long, long long>::iterator it = Fmap.find(n); if (it != Fmap.end()) { return it->second; } if ((n & 1) == 1) { long long f1 = FIB((n + 1) / 2); long long f2 = FIB((n - 1) / 2); long long res = (sqrMod(f1) + sqrMod(f2)) % (1000000000LL*1000000000LL); Fmap[n] = res; return res; } else { long long f1 = FIB((n / 2) + 1); long long f2 = FIB((n / 2) - 1); long long res = (sqrMod(f1) - sqrMod(f2) + (1000000000LL*1000000000LL)) % (1000000000LL*1000000000LL); Fmap[n] = res; return res; } } int main() { char str[100]; scanf("%s", str); int dig = 0; while (str[dig] != 0) { dig++; } // printf("FIB:%lld\n", FIB(45LL)); /* for (int i = 0; i < 1000; i++) { printf("%i:%lld\n", i, FIB(i)); } */ cykl[0] = 1; offsetCnt[0] = 1; offset[0][0] = 0; long long mask = 1; int d = 1; while (d <= dig) { mask *= 10; long long i = cykl[d - 1]; while ((FIB(i) % mask) != 0 || (FIB(i + 1) % mask) != 1) { i += cykl[d - 1]; } cykl[d] = i; //printf("CYKL:%i %lld\n", d, cykl[d]); d++; } mask = 1; d = 1; long long val = 0; while (d <= dig) { offsetCnt[d] = 0; val += mask * (str[dig - d] - '0'); mask *= 10; long long p = 0; while (p < cykl[d]) { for (int i = 0; i < offsetCnt[d - 1]; i++) { if ((FIB(p + offset[d - 1][i]) % mask) == val) { offset[d][offsetCnt[d]] = p + offset[d - 1][i]; offsetCnt[d]++; } } p += cykl[d - 1]; } d++; } if (offsetCnt[dig] > 0) { printf("%lld\n", offset[dig][offsetCnt[dig] - 1]); //printf("%s %lld -> %lld\n", str, offset[dig][offsetCnt[dig] - 1], FIB(offset[dig][offsetCnt[dig] - 1])); } else { printf("NIE\n"); } return 0; } |