#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned char uc; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; typedef pair<ull,ull> pull; typedef pair<pull,pull> macierz; char s[25]; int n; ull w,co,m; ull pomnoz(ull a,ull b){ull w=0;while(b){if(b&1)w=(w+a)%m;a=(a<<1)%m;b>>=1;}return w;} ull pot(ull a,ull b){ull w=1;while(b){if(b&1)w*=a;a*=a;b>>=1;}return w;} inline macierz jedn() { macierz ret; ret.e1.e1=ret.e2.e2=1; return ret; } macierz operator*(macierz a,macierz b) { macierz ret; ret.e1.e1=(pomnoz(a.e1.e1,b.e1.e1)+pomnoz(a.e1.e2,b.e2.e1))%m; ret.e1.e2=(pomnoz(a.e1.e1,b.e1.e2)+pomnoz(a.e1.e2,b.e2.e2))%m; ret.e2.e1=(pomnoz(a.e2.e1,b.e1.e1)+pomnoz(a.e2.e2,b.e2.e1))%m; ret.e2.e2=(pomnoz(a.e2.e1,b.e1.e2)+pomnoz(a.e2.e2,b.e2.e2))%m; return ret; } macierz pot(macierz a,ull b){macierz w=jedn();while(b){if(b&1)w=w*a;a=a*a;b>>=1;}return w;} ull fib(ull a,ull modulo) { if (!a) return 0; macierz s; s.e1.e1=s.e1.e2=s.e2.e1=1; m=modulo; s=pot(s,a); return s.e1.e2; } void dfs(ull a,int ile) { if (ile==n) printf("150000000000000000000%llu",a),exit(0); ull mod=pot(10,++ile); if (ile==1) FOR(i,0,59){ if (fib(i,mod)==(uc)s[n]) dfs(i,ile); } else if (ile==2) FOR(i,0,4){ if (fib(a+i*60,mod)/(mod/10)==(uc)s[n-1]) dfs(a+i*60,ile); } else if (ile==3) FOR(i,0,4){ if (fib(a+i*300,mod)/(mod/10)==(uc)s[n-2]) dfs(a+i*300,ile); } else { ll v=15*pot(10,ile-2); FOR(i,0,9) if (fib(a+i*v,mod)/(mod/10)==(uc)s[n-ile+1]) dfs(a+i*v,ile); } } int main() { gets(s+1); n=strlen(s+1); FOR(i,1,n) s[i]-=48; dfs(0,0); puts("NIE"); }
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 | #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned char uc; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; typedef pair<ull,ull> pull; typedef pair<pull,pull> macierz; char s[25]; int n; ull w,co,m; ull pomnoz(ull a,ull b){ull w=0;while(b){if(b&1)w=(w+a)%m;a=(a<<1)%m;b>>=1;}return w;} ull pot(ull a,ull b){ull w=1;while(b){if(b&1)w*=a;a*=a;b>>=1;}return w;} inline macierz jedn() { macierz ret; ret.e1.e1=ret.e2.e2=1; return ret; } macierz operator*(macierz a,macierz b) { macierz ret; ret.e1.e1=(pomnoz(a.e1.e1,b.e1.e1)+pomnoz(a.e1.e2,b.e2.e1))%m; ret.e1.e2=(pomnoz(a.e1.e1,b.e1.e2)+pomnoz(a.e1.e2,b.e2.e2))%m; ret.e2.e1=(pomnoz(a.e2.e1,b.e1.e1)+pomnoz(a.e2.e2,b.e2.e1))%m; ret.e2.e2=(pomnoz(a.e2.e1,b.e1.e2)+pomnoz(a.e2.e2,b.e2.e2))%m; return ret; } macierz pot(macierz a,ull b){macierz w=jedn();while(b){if(b&1)w=w*a;a=a*a;b>>=1;}return w;} ull fib(ull a,ull modulo) { if (!a) return 0; macierz s; s.e1.e1=s.e1.e2=s.e2.e1=1; m=modulo; s=pot(s,a); return s.e1.e2; } void dfs(ull a,int ile) { if (ile==n) printf("150000000000000000000%llu",a),exit(0); ull mod=pot(10,++ile); if (ile==1) FOR(i,0,59){ if (fib(i,mod)==(uc)s[n]) dfs(i,ile); } else if (ile==2) FOR(i,0,4){ if (fib(a+i*60,mod)/(mod/10)==(uc)s[n-1]) dfs(a+i*60,ile); } else if (ile==3) FOR(i,0,4){ if (fib(a+i*300,mod)/(mod/10)==(uc)s[n-2]) dfs(a+i*300,ile); } else { ll v=15*pot(10,ile-2); FOR(i,0,9) if (fib(a+i*v,mod)/(mod/10)==(uc)s[n-ile+1]) dfs(a+i*v,ile); } } int main() { gets(s+1); n=strlen(s+1); FOR(i,1,n) s[i]-=48; dfs(0,0); puts("NIE"); } |