#include <iostream> using namespace std; unsigned long long fibo(int n) { unsigned long long q11,q12,q21,q22, p11,p12,p21,p22, w11,w12,w21,w22; if(n < 2) return n; q11 = q12 = q21 = 1; q22 = 0; w11 = w22 = 1; w12 = w21 = 0; n--; while(n) { if(n & 1) { p11 = w11*q11 + w12 * q21; p12 = w11*q12 + w12 * q22; p21 = w21*q11 + w22 * q21; p22 = w21*q12 + w22 * q22; w11 = p11; w12 = p12; w21 = p21; w22 = p22; } n >>= 1; if(!n) break; p11 = q11*q11 + q12 * q21; p12 = q11*q12 + q12 * q22; p21 = q21*q11 + q22 * q21; p22 = q21*q12 + q22 * q22; q11 = p11; q12 = p12; q21 = p21; q22 = p22; } return w11; } int main() { int aa, a, b, dl = 1, c = 0; unsigned long long i = 0; cin >> a; if(a == 0) { cout << 0; exit(0); } aa = a; while(aa>0) { aa -= aa % dl; dl *= 10; } dl /= 10; while(i <= 18446744073709551614) { if(a == fibo(i) % dl){cout << i; exit(0);} if(a % 8 == 0) i += 6; else if(a % 2 == 0) i += 3; else if(a % 5 == 0) i += 5; else i++; } cout << "NIE"; 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 | #include <iostream> using namespace std; unsigned long long fibo(int n) { unsigned long long q11,q12,q21,q22, p11,p12,p21,p22, w11,w12,w21,w22; if(n < 2) return n; q11 = q12 = q21 = 1; q22 = 0; w11 = w22 = 1; w12 = w21 = 0; n--; while(n) { if(n & 1) { p11 = w11*q11 + w12 * q21; p12 = w11*q12 + w12 * q22; p21 = w21*q11 + w22 * q21; p22 = w21*q12 + w22 * q22; w11 = p11; w12 = p12; w21 = p21; w22 = p22; } n >>= 1; if(!n) break; p11 = q11*q11 + q12 * q21; p12 = q11*q12 + q12 * q22; p21 = q21*q11 + q22 * q21; p22 = q21*q12 + q22 * q22; q11 = p11; q12 = p12; q21 = p21; q22 = p22; } return w11; } int main() { int aa, a, b, dl = 1, c = 0; unsigned long long i = 0; cin >> a; if(a == 0) { cout << 0; exit(0); } aa = a; while(aa>0) { aa -= aa % dl; dl *= 10; } dl /= 10; while(i <= 18446744073709551614) { if(a == fibo(i) % dl){cout << i; exit(0);} if(a % 8 == 0) i += 6; else if(a % 2 == 0) i += 3; else if(a % 5 == 0) i += 5; else i++; } cout << "NIE"; return 0; } |