{"id":65,"date":"2011-03-29T07:40:27","date_gmt":"2011-03-28T23:40:27","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=65"},"modified":"2012-03-03T07:43:36","modified_gmt":"2012-03-02T23:43:36","slug":"uva-756-biorhythms","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/uva-756-biorhythms\/","title":{"rendered":"UVa 756. Biorhythms"},"content":{"rendered":"

Breif description :<\/h3>\n

Give you a system of modular arithmetic equation ..
\nYour task is to calculate the minimum solution.
\n<\/p>\n

Analyse :<\/h3>\n

Solve the system of the modular arithmetic equation is a fundament in Number Theroy<\/a>, There is a method called Chinese Remainder Theorem<\/a> could give us a good answer.<\/p>\n

\r\n#include \r\n#include \r\nusing namespace std;\r\n\r\nconst int M1 = 23 , M2 = 28, M3 = 33, M = M1 * M2 * M3;\r\nint m1, m2, m3, mm1, mm2, mm3, c1, c2, c3;\r\nint r1, r2, r3, x0;\r\nint n, a;\r\n\r\n\r\ninline void _M(int &a){\r\n\tif (a < 0) a += M;\r\n\ta %= M;\r\n}\r\n\r\ninline int _M(const int& a, const int& n){\r\n\tif (a < 0) return a + n;\r\n\treturn a;\r\n}\r\n\r\ninline int _I(int b, const int& n){\r\n\tint a = n;\r\n\tint x1 = 0, x2 = 1, q;\r\n\twhile (true){\r\n\t\tq = a \/ b, a %= b;\r\n\t\tif (!a) return _M(x2, n);\r\n\t\tx1 -= q * x2;\r\n\t\tq = b \/ a, b %= a;\r\n\t\tif (!b) return _M(x1, n);\r\n\t\tx2 -= q * x1;\r\n\t}\r\n}\r\n\r\ninline int _CRT(){\r\n\tint res = r1 * c1; _M(res);\r\n\tres += r2 * c2, _M(res);\r\n\tres += r3 * c3, _M(res);\r\n\tres -= x0, _M(res);\r\n\treturn res;\r\n}\r\n\r\n\r\n\r\n\r\nint main(){\r\n\tm1 = M \/ M1, m2 = M \/ M2, m3 = M \/ M3;\r\n\tmm1 = _I(m1, M1), mm2 = _I(m2, M2), mm3 =  _I(m3, M3);\r\n\tc1 = _M(m1 * mm1, M), c2 = _M(m2 * mm2, M), c3 = _M(m3 * mm3, M);\r\n\t\r\n\tint T = 0;\r\n\twhile (cin >> n && n!=0){\r\n\t\tprintf(\"Case %d: the next triple peak occurs in %d days.\\n\", ++T, _CRT() ? _CRT() : M);\r\n\t}\r\n}\r\n<\/pre>\n
<\/bk><\/bk><\/p>\n
Further discussion :<\/h3>\n
This problem has fixed modulus, which makes it more appropriate to do so, but … Implement the algorithm naively according to the original CRT has a few restriction.[nbnote ]
\n
\nHere have another method called Merge-Equation Could extend its scope, which is equivalence on principle, different on motivation  …<\/a>[\/nbnote] <\/p>\n
Here we give another iteration algorithm :<\/p>\n
 int x = r[0], step = m[0];\r\n for (int i = 1; i < n; i ++){\r\n\twhile ((x - a[i]) % m[i] != r[i])\r\n\t\tx += step;\r\n\tstep = lcm(step, m[i]);\r\n }<\/pre>\n
 This algorithm is base on the brute force enumerate method, The inner while loop actually is to solve the following equation:<\/p>\n
 x + ? step = r[i] (mod m[i])<\/p>\n
 ... And this step could work out with a exEuclid algorithm which is similar to the previous one... <\/p>\n
The method maybe more straight and powerful (faster?), to taste those subtle distinction, try UVa 700. Date Bugs<\/a> ... (or Poj ???)<\/p>\n
External link :<\/h3>\n