#include<cstdio> #include<cstring> #define llu unsigned long long struct mac { llu pg,pd,lg,ld; }; llu mnoz(llu a1,llu a2) { llu o=0; for(int i=0;i<64;i++) { if(a2&(1llu<<i))o=(o+a1)%1000000000000000000ll; a1=(2*a1)%1000000000000000000ll; } return o; } mac operator*(mac a1,mac a2) { mac o; o.pg=(mnoz(a1.lg,a2.pg)+mnoz(a1.pg,a2.pd))%1000000000000000000ll; o.lg=(mnoz(a1.lg,a2.lg)+mnoz(a1.pg,a2.ld))%1000000000000000000ll; o.pd=(mnoz(a1.pd,a2.pd)+mnoz(a1.ld,a2.pg))%1000000000000000000ll; o.ld=o.pg; return o; } llu sk1[21],il[21],spr,suf,wyn; int l; char d[100]; mac nullmac,mt,prim,mpt[100]; mac pot(mac m1,llu pt) { mac o=m1; pt--; for(int i=0;i<64;i++)if(pt&(1llu<<i))o=o*mpt[i]; return o; } int main() { prim.lg=1;prim.pg=1;prim.ld=1; scanf("%s",d); l=strlen(d); spr=1; for(int i=0;i<l;i++)spr*=10; mpt[0]=prim; for(int i=1;i<64;i++)mpt[i]=mpt[i-1]*mpt[i-1]; for(int i=0;i<l;i++)suf=suf*10+d[i]-48; sk1[0]=1;sk1[1]=15;sk1[2]=150;sk1[3]=1500; for(int i=4;i<=18;i++)sk1[i]=sk1[i-1]*10; mt=prim; llu p1=1; llu p2=1; wyn=1; while(p1!=suf) { llu p3=(p1+p2)%spr; p1=p2; p2=p3; wyn++; if(wyn==10000000){printf("NIE");return 0;} } for(int i=0;i<=20;i++)wyn+=sk1[i]*il[i]; printf("%lld\n",wyn); }
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 | #include<cstdio> #include<cstring> #define llu unsigned long long struct mac { llu pg,pd,lg,ld; }; llu mnoz(llu a1,llu a2) { llu o=0; for(int i=0;i<64;i++) { if(a2&(1llu<<i))o=(o+a1)%1000000000000000000ll; a1=(2*a1)%1000000000000000000ll; } return o; } mac operator*(mac a1,mac a2) { mac o; o.pg=(mnoz(a1.lg,a2.pg)+mnoz(a1.pg,a2.pd))%1000000000000000000ll; o.lg=(mnoz(a1.lg,a2.lg)+mnoz(a1.pg,a2.ld))%1000000000000000000ll; o.pd=(mnoz(a1.pd,a2.pd)+mnoz(a1.ld,a2.pg))%1000000000000000000ll; o.ld=o.pg; return o; } llu sk1[21],il[21],spr,suf,wyn; int l; char d[100]; mac nullmac,mt,prim,mpt[100]; mac pot(mac m1,llu pt) { mac o=m1; pt--; for(int i=0;i<64;i++)if(pt&(1llu<<i))o=o*mpt[i]; return o; } int main() { prim.lg=1;prim.pg=1;prim.ld=1; scanf("%s",d); l=strlen(d); spr=1; for(int i=0;i<l;i++)spr*=10; mpt[0]=prim; for(int i=1;i<64;i++)mpt[i]=mpt[i-1]*mpt[i-1]; for(int i=0;i<l;i++)suf=suf*10+d[i]-48; sk1[0]=1;sk1[1]=15;sk1[2]=150;sk1[3]=1500; for(int i=4;i<=18;i++)sk1[i]=sk1[i-1]*10; mt=prim; llu p1=1; llu p2=1; wyn=1; while(p1!=suf) { llu p3=(p1+p2)%spr; p1=p2; p2=p3; wyn++; if(wyn==10000000){printf("NIE");return 0;} } for(int i=0;i<=20;i++)wyn+=sk1[i]*il[i]; printf("%lld\n",wyn); } |