{"id":96,"date":"2011-08-02T22:55:00","date_gmt":"2011-08-02T14:55:00","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=96"},"modified":"2020-06-03T22:56:07","modified_gmt":"2020-06-03T14:56:07","slug":"zoj-1962-how-many-fibs","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=96","title":{"rendered":"zoj 1962 How Many Fibs"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/\/\u4e0d\u591f\u7cbe\u7b80\uff0c\u6548\u7387\u4e5f\u4e0d\u9ad8\uff0c\u4ee5\u540e\u5b66\u4e86\u5085\u91cc\u53f6\u53d8\u6362\u518d\u505a\u5427\u3002\u3002\u3002 \n#define LOCAL\n#include&lt;iostream>\n#include&lt;cstring>\n#define N 1001\nusing namespace std;\nint cmp(int a&#91;N],string s)\n{\n       char t;\n       string b=s;\n       int i,la,lb=b.size();\n       for(i=0;i&lt;lb\/2;i++)\n       {\n              t=b&#91;i];\n              b&#91;i]=b&#91;lb-i-1];\n              b&#91;lb-i-1]=t;            \n       }\n       lb--;\n       la=N-1;\n       while(!a&#91;la]) la--;\n       if(la>lb)\n          return 1;\n       else if(la&lt;lb)\n          return -1;\n       else\n       {\n            if(a&#91;la]==(b&#91;la]-'0')) \/\/\u8fd9\u91cc\u7684\u5224\u65ad\u4e5f\u51fa\u4e86\u9519\u8bef\u3002\u3002\u3002 \n            {\n                   i=la;\n                   while(a&#91;i]==(b&#91;i]-'0')&amp;&amp;i>=0) i--;\n                   if(i&lt;0)\n                         return 0;\n                   else if(a&#91;i]>(b&#91;i]-'0'))\n                           return 1;\n                   else return -1;                    \n            }\n            else if(a&#91;la]>(b&#91;la]-'0'))\n                return 1;\n            else return -1;     \n       }\n          \n}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n    int sum&#91;N],a&#91;N],b&#91;N],n,i,t,count;\n    string x,y;\n    while(cin>>x>>y)\n    {\n        if(x==\"0\"&amp;&amp;y==\"0\")\n              return 0;\n        memset(a,0,sizeof(a));\n        memset(b,0,sizeof(b));\n        memset(sum,0,sizeof(sum));\n        b&#91;0]=1;\n        count=0;\n        while(1)\n        {\n           for(i=0;i&lt;N;i++)\n              sum&#91;i]=a&#91;i]+b&#91;i];\n           for(i=0;i&lt;N;i++)\n           {\n              t=sum&#91;i]\/10;\n              sum&#91;i]=sum&#91;i]%10;\n              sum&#91;i+1]+=t;                \n            }   \n            if(cmp(sum,x)>=0&amp;&amp;cmp(sum,y)&lt;=0)   \/\/cmp()\u4e00\u76f4\u51fa\u9519\uff0c\u54ce\u3002\u3002\u3002 \n                 count++;\n            else if(cmp(sum,y)>0)   \/\/\u8fd9\u7684\u6761\u4ef6\u5f04\u9519\u4e86\uff0c\u7ea0\u7ed3\u4e86\u597d\u534a\u5929\u3002\u3002\u3002 \n                 break;\n            memcpy(a,b,sizeof(int)*N);\n            memcpy(b,sum,sizeof(int)*N);            \n        }\n        cout&lt;&lt;count&lt;&lt;endl;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-96","post","type-post","status-publish","format-standard","hentry","category-06-01-acm"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/96","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=96"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/96\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=96"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=96"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=96"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}