#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<bitset> using namespace std; #define inf 1000000005 typedef long long ll; typedef double db; void gn(int &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } void gn(ll &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } ll mo; int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int gcd(int a,int b){return b?gcd(b,a%b):a;} ll mul(ll a,ll b){a>=mo?a%=mo:0;b>=mo?b%=mo:0;ll ans=0;do{if(b&1)(ans+=a)>=mo?ans-=mo:0;(a+=a)>=mo?a-=mo:0;}while(b>>=1);return ans;} struct mat{ll a,b,c,d;}; mat operator*(const mat&x,const mat&y){ return (mat){(mul(x.a,y.a)+mul(x.b,y.c))%mo,(mul(x.a,y.b)+mul(x.b,y.d))%mo, (mul(x.c,y.a)+mul(x.d,y.c))%mo,(mul(x.c,y.b)+mul(x.d,y.d))%mo}; } mat po(mat x,ll p){ mat ans=(mat){1,0,0,1}; do{ if(p&1)ans=ans*x; x=x*x; }while(p>>=1); return ans; } ll fib(ll n){ mat x=(mat){1,1,1,0}; x=po(x,n); return x.c; } ll f[1000000]; int n; ll r; ll m2,m5; ll r2[1000000],r5[100]; int r2tot=0,r5tot=0; int r2ok[1000000]={0}; void test(ll x){ mo=1; for (int i=1;i<=n;i++)mo*=10; ll y=fib(x); if(r==y)printf("yes\n"); else printf("no\n"); } int work(ll x){ ll cur=x; for (int i=0;i<m2;i++){ if(r2ok[cur%m2]){ while(cur<1000)cur+=m2*m5; cout<<cur<<endl; //test(cur); return 1; } cur+=m5; } return 0; } int main() { char s[20]; scanf("%s",s+1); n=strlen(s+1); r=0; for (int i=1;i<=n;i++)r=r*10+s[i]-'0'; mo=1; for (int i=1;i<=n;i++)mo*=2; f[0]=0;f[1]=1; for (int i=2;;i++){ f[i]=(f[i-1]+f[i-2])%mo; if(f[i-1]==0 && f[i]==1){ m2=i-1; break; } } ll d2=r%mo; for (int ii=0;ii<m2;ii++)if(f[ii]==d2){ r2[++r2tot]=ii; r2ok[ii]=1; } if(r2tot){ for (int i=2;i<20;i++){ f[i]=(f[i-1]+f[i-2])%5; } for (int j=0;j<20;j++)if(f[j]==r%5){ ll xx=j; m5=20;mo=5; for (int i=2;i<=n;i++){ mo*=5;ll d5=r%mo; while(fib(xx)!=d5)xx+=m5; m5*=5; } r5[++r5tot]=xx; } for (int i=1;i<=r5tot;i++)if(work(r5[i]))return 0; printf("NIE\n"); }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 122 123 124 | #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<bitset> using namespace std; #define inf 1000000005 typedef long long ll; typedef double db; void gn(int &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } void gn(ll &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } ll mo; int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int gcd(int a,int b){return b?gcd(b,a%b):a;} ll mul(ll a,ll b){a>=mo?a%=mo:0;b>=mo?b%=mo:0;ll ans=0;do{if(b&1)(ans+=a)>=mo?ans-=mo:0;(a+=a)>=mo?a-=mo:0;}while(b>>=1);return ans;} struct mat{ll a,b,c,d;}; mat operator*(const mat&x,const mat&y){ return (mat){(mul(x.a,y.a)+mul(x.b,y.c))%mo,(mul(x.a,y.b)+mul(x.b,y.d))%mo, (mul(x.c,y.a)+mul(x.d,y.c))%mo,(mul(x.c,y.b)+mul(x.d,y.d))%mo}; } mat po(mat x,ll p){ mat ans=(mat){1,0,0,1}; do{ if(p&1)ans=ans*x; x=x*x; }while(p>>=1); return ans; } ll fib(ll n){ mat x=(mat){1,1,1,0}; x=po(x,n); return x.c; } ll f[1000000]; int n; ll r; ll m2,m5; ll r2[1000000],r5[100]; int r2tot=0,r5tot=0; int r2ok[1000000]={0}; void test(ll x){ mo=1; for (int i=1;i<=n;i++)mo*=10; ll y=fib(x); if(r==y)printf("yes\n"); else printf("no\n"); } int work(ll x){ ll cur=x; for (int i=0;i<m2;i++){ if(r2ok[cur%m2]){ while(cur<1000)cur+=m2*m5; cout<<cur<<endl; //test(cur); return 1; } cur+=m5; } return 0; } int main() { char s[20]; scanf("%s",s+1); n=strlen(s+1); r=0; for (int i=1;i<=n;i++)r=r*10+s[i]-'0'; mo=1; for (int i=1;i<=n;i++)mo*=2; f[0]=0;f[1]=1; for (int i=2;;i++){ f[i]=(f[i-1]+f[i-2])%mo; if(f[i-1]==0 && f[i]==1){ m2=i-1; break; } } ll d2=r%mo; for (int ii=0;ii<m2;ii++)if(f[ii]==d2){ r2[++r2tot]=ii; r2ok[ii]=1; } if(r2tot){ for (int i=2;i<20;i++){ f[i]=(f[i-1]+f[i-2])%5; } for (int j=0;j<20;j++)if(f[j]==r%5){ ll xx=j; m5=20;mo=5; for (int i=2;i<=n;i++){ mo*=5;ll d5=r%mo; while(fib(xx)!=d5)xx+=m5; m5*=5; } r5[++r5tot]=xx; } for (int i=1;i<=r5tot;i++)if(work(r5[i]))return 0; printf("NIE\n"); }else printf("NIE\n"); return 0; } |