{"id":512,"date":"2013-09-04T13:30:10","date_gmt":"2013-09-04T05:30:10","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=512"},"modified":"2013-09-04T13:30:10","modified_gmt":"2013-09-04T05:30:10","slug":"hdoj1005-number-sequence","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=512","title":{"rendered":"HDOJ1005 Number Sequence"},"content":{"rendered":"<p><span><b>Time Limit: 2000\/1000 MS (Java\/Others)\u00a0\u00a0\u00a0\u00a0Memory Limit: 65536\/32768 K (Java\/Others)<br \/>\nTotal Submission(s): 84538\u00a0\u00a0\u00a0\u00a0Accepted Submission(s): 20059<br \/>\n<\/b><\/span><\/p>\n<div align=\"left\">Problem Description<\/div>\n<div>A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n &#8211; 1) + B * f(n &#8211; 2)) mod 7.<br \/>\nGiven A, B, and n, you are to calculate the value of f(n).\n<\/div>\n<div><\/div>\n<p>&nbsp;<\/p>\n<div align=\"left\">Input<\/div>\n<div>The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 &lt;= A, B &lt;= 1000, 1 &lt;= n &lt;= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.<\/div>\n<div><\/div>\n<p>&nbsp;<\/p>\n<div align=\"left\">Output<\/div>\n<div>For each test case, print the value of f(n) on a single line.<\/div>\n<div><\/div>\n<p>&nbsp;<\/p>\n<div align=\"left\">Sample Input<\/div>\n<div>\n<div>1 1 3 1 2 10 0 0 0<\/div>\n<\/div>\n<div><\/div>\n<p>&nbsp;<\/p>\n<div align=\"left\">Sample Output<\/div>\n<div>\n<div>2 5<\/div>\n<\/div>\n<div><\/div>\n<p>&nbsp;<br \/>\n===========================================<br \/>\n\u6309\u7167PPT\u91cc\u9762\u7684\u8bf4\u6cd5\uff0c\u5c31\u662f\u201c\u5bf9\u4e8e\u8fd9\u79cd\u9898\u76ee\uff0c\u5343\u4e07\u4e0d\u80fd\u86ee\u5e72\uff01\u5b9e\u9645\u4e0a\uff0c\u6709\u7ecf\u9a8c\u7684\u540c\u5b66\u770b\u5230\u672c\u9898\u76ee\u7684\u6570\u636e\u89c4\u6a21\uff0c\u5f88\u5feb\u5c31\u80fd\u77e5\u9053\uff1a\u8fd9\u7c7b\u9898\u76ee\u6709\u89c4\u5f8b\u53ef\u5faa\u3002\u201d<br \/>\n\u7531\u4e8e\u662fmod7\u7684\u5173\u7cfb\uff0c\u51fd\u6570f\u4e24\u4e2a\u53c2\u6570\uff0c\u90fd\u662f0~6\u8303\u56f4\u5185\u7684\uff0c\u6240\u4ee5\u5171\u8ba17*7=49\u79cd\u53ef\u80fd\u6027\uff0c\u8fd9\u662f\u5176\u4e00\uff0c\u907f\u514d\u91cd\u590d\u8ba1\u7b97\u3002<br \/>\n\u5176\u4e8c\uff0chttp:\/\/www.cnblogs.com\/Lyush\/archive\/2011\/09\/04\/2165927.html\u91cc\u9762\u6240\u8bf4\u4e00\u822c\uff0c\u8fd9\u79cd\u4e1c\u897f\u80af\u5b9a\u662f\u6709\u5faa\u73af\u7684\uff0c\u5faa\u73af\u8282\u6700\u592750\uff0c\u4f55\u65f6\u627e\u5230\u5faa\u73af\u5462\uff1f\u4e24\u4e2a\u53c2\u6570\u4e00\u6837\u7684\u65f6\u5019\u5457\u3002\u8fd9\u4e2a\u95ee\u9898\u56f0\u6270\u4e86\u6211\u4e00\u665a\u4e0a\uff0c\u4eca\u5929\u65e9\u4e0a\u5b9e\u5728\u5fcd\u4e0d\u4f4f\u641c\u535a\u5ba2\u641c\u5230\u4e86&#8230;\u6240\u4ee5\u81ea\u5df1\u8fd8\u662f\u592a\u5e74\u8f7b\u4e86\u5427<br \/>\n\u8fd9\u4e24\u70b9\u641e\u5b9a\u4e86\uff0c\u5c31\u6ca1\u6709\u4efb\u4f55\u95ee\u9898\u4e86\u3002<\/p>\n<pre>\n#include <iostream>\nusing namespace std;\nint f(int A, int B, unsigned long n)\n{\n    if(n == 2 || n == 1)\n        return 1;\n    int mat[7][7];\n    int looked[7][7];\n    for(int i=0; i<7; i++)\n    {\n        for(int j=0; j<7; j++)\n        {\n            mat[i][j] = (A*i+B*j)%7;\n            looked[i][j] = 0;\n        }\n    }\n    int last_2 = 1;\n    int last_1 = 1;\n    looked[1][1] = 2;\n    unsigned long next = n;\n    for(unsigned long m=3; m<=next; m++)\n    {\n        int curr = mat[last_1][last_2];\n        last_2 = last_1;\n        last_1 = curr;\n        if(looked[last_1][last_2] > 0)\n        {\n            \/\/\u5f00\u59cb\u5faa\u73af\u4e86\uff01\n            next = (n - looked[last_1][last_2])%(m - looked[last_1][last_2]) + m;\n        }\n        looked[last_1][last_2] = m;\n    }\n    return last_1;\n}\nint main()\n{\n    int A, B;\n    unsigned long n;\n    while(cin >> A >> B >> n && A+B+n != 0)\n    {\n        cout << f(A, B, n) << endl;\n    }\n    return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Time Limit: 2000\/1000 MS (Java\/Others)\u00a0\u00a0\u00a0\u00a0Memory Limit: 65536\/32768 K (Java\/Others) Total Submission(s): 84538\u00a0\u00a0\u00a0\u00a0Accepted Submission(s): 20059 Problem Description A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n &#8211; 1) + B * f(n &#8211; 2)) mod 7. Given A, B, and n, you are to calculate the value of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[138],"class_list":["post-512","post","type-post","status-publish","format-standard","hentry","category-study","tag-other-cpp"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/512","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=512"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}