{"id":349994,"date":"2023-07-09T09:00:52","date_gmt":"2023-07-09T09:00:52","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=349994"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=349994","title":{"rendered":"<span>\u0412\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430 \u043b\u0438\u0442\u043a\u043e\u0434\u0435: \u0412\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043f\u043e\u043a\u0443\u043f\u043a\u0438 \u0434\u0432\u0443\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0415\u0441\u0442\u044c \u0432\u043e\u0442 \u0442\u0430\u043a\u0430\u044f, \u0432\u0440\u043e\u0434\u0435 \u0431\u044b, \u043f\u0440\u043e\u0441\u0442\u0430\u044f <a href=\"https:\/\/leetcode.com\/problems\/number-of-ways-to-buy-pens-and-pencils\/description\/\" rel=\"noopener noreferrer nofollow\">\u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430 \u043b\u0438\u0442\u043a\u043e\u0434\u0435<\/a>: \u0414\u0430\u043d\u043e \u0442\u0440\u0438 \u0447\u0438\u0441\u043b\u0430 <code>total<\/code> &#8212; \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0443 \u0432\u0430\u0441 \u0435\u0441\u0442\u044c \u0434\u0435\u043d\u0435\u0433, <code>cost1<\/code>, <code>cost2<\/code> &#8212; \u0446\u0435\u043d\u044b \u0434\u0432\u0443\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432. \u041d\u0430\u0434\u043e \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u0435\u0433\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u043a\u0443\u043f\u0438\u0442\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e-\u0442\u043e \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432, \u043d\u0435 \u0432\u044b\u0445\u043e\u0434\u044f \u0438\u0437 \u0431\u044e\u0434\u0436\u0435\u0442\u0430 (\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u043c\u0435\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u043a\u0443\u043f\u043e\u043a, \u0430 \u043d\u0435 \u043f\u043e\u0440\u044f\u0434\u043e\u043a). \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u0442 \u0446\u0435\u043b\u044b\u0445 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u0430\u0440 (x, y), \u0442\u0430\u043a\u0438\u0445 \u0447\u0442\u043e <code>x*cost1+y*cost2 &lt;= total<\/code> . \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0438\u043c\u0435\u044f \u0442\u043e\u0432\u0430\u0440\u044b \u0446\u0435\u043d\u0430\u043c\u0438 {5, 10} \u0438 20 \u0434\u0435\u043d\u0435\u0433 \u043d\u0430 \u0440\u0443\u043a\u0430\u0445, \u0435\u0441\u0442\u044c 9 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0434\u0435\u043d\u044c\u0433\u0438: 0, 5, 5+5, 5+5+5, 5+5+5+5, 10, 10+5, 10+5+5, 10+10.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0434\u0430\u0436\u0435 \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u0430 \u043a\u0430\u043a medium, \u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u043e\u0447\u0442\u0438 \u0432 \u043e\u0434\u043d\u0443 \u0441\u0442\u0440\u043e\u0447\u043a\u0443 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f, \u043d\u043e \u044d\u0442\u043e \u0435\u0441\u043b\u0438 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0431\u0435\u0437\u0443\u043c\u043d\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430 <code>O(min(cost1, cost2))<\/code>, \u0442.\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043e\u0442 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u0410 \u0441\u043c\u043e\u0436\u0435\u0442\u0435 \u043b\u0438 \u0432\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u0435\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 &#8212; \u0437\u0430 <code>O(log(max(cost1, cost2)))<\/code> ? \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0437\u0430\u0434\u0430\u0447\u043a\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0432\u043f\u043e\u043b\u043d\u0435 \u0441\u0435\u0431\u0435 hard \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438, \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438 \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e\u0441\u0442\u0438. \u0415\u0441\u043b\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0434\u043e\u0431\u0440\u043e \u043f\u043e\u0436\u0430\u043b\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0434 \u043a\u0430\u0442. \u0411\u0443\u0434\u0443 \u0440\u0430\u0434 \u043b\u044e\u0431\u044b\u043c \u0430\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u043d\u044b\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c. \u041c\u043e\u0436\u0435\u0442 \u043a\u0442\u043e-\u0442\u043e \u0441\u043c\u043e\u0436\u0435\u0442 \u0434\u043e\u0434\u0443\u043c\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u043f\u043e\u0445\u043e\u0436\u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0449\u0435.<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435 \u043f\u043e \u043e\u0444\u043e\u0440\u043c\u043b\u0435\u043d\u0438\u044e<\/summary>\n<div class=\"spoiler__content\">\n<p>\u042f \u0431\u0443\u0434\u0443 \u0430\u043a\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f &#171;\u0430\u0431\u0431\u0440\u0435\u0432\u0438\u0430\u0442\u0443\u0440\u0430\u043c\u0438&#187; \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435: \u0432\u0441\u044f\u043a\u043e\u0435 \u043d\u0443\u0434\u043d\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u044f \u0431\u0443\u0434\u0443 \u043f\u0440\u044f\u0442\u0430\u0442\u044c \u0432 \u043d\u0438\u0445. \u0415\u0441\u043b\u0438 \u0432\u044b \u0432\u0438\u0434\u0438\u0442\u0435 \u043f\u043e\u0434\u0447\u0435\u0440\u043a\u043d\u0443\u0442\u043e\u0435 \u0441\u043b\u043e\u0432\u043e &#171;<abbr class=\"habraabbr\" title=\"\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e \u0436\u0435!\" data-title=\"&lt;p>\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e \u0436\u0435!&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr>&#171;, \u043d\u0430\u0432\u0435\u0434\u0438\u0442\u0435 \u0442\u0443\u0434\u0430 \u043c\u044b\u0448\u043a\u0443 \u0438 \u0431\u043e\u043b\u0435\u0435 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u0441\u043f\u043b\u044b\u0442\u044c \u0432 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043a\u0435.<\/p>\n<\/div>\n<\/details>\n<h2>\u0421\u0432\u043e\u0434\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0441\u0443\u043c\u043c\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430<\/h2>\n<p>\u0418\u0442\u0430\u043a, \u0434\u043b\u044f \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0438 \u0431\u0443\u043a\u0432 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u0432\u0435\u0434\u0435\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f: <code>a<\/code>, <code>b<\/code> &#8212; \u0446\u0435\u043d\u044b \u0442\u043e\u0432\u0430\u0440\u043e\u0432, <code>c<\/code> &#8212; \u0441\u0443\u043c\u043c\u0430 \u043d\u0430 \u0440\u0443\u043a\u0430\u0445. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e <code>GCD(a,b)=1<\/code>, \u0438\u043d\u0430\u0447\u0435 <abbr class=\"habraabbr\" title=\"\u041d\u0443 \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0432\u0441\u0435 \u0446\u0435\u043d\u044b \u0443\u043a\u0430\u0437\u0430\u043d\u044b \u043d\u0435 \u0432 \u0435\u0434\u0438\u043d\u0438\u0446\u0430\u0445 \u0434\u0435\u043d\u0435\u0433, \u0430 \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043c\u043e\u043d\u0435\u0442 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u043e\u043c. \u0411\u044e\u0434\u0436\u0435\u0442 \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u044d\u0442\u0438\u0445 \u043c\u043e\u043d\u0435\u0442\u0430\u0445, \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043a\u043e\u043f\u0435\u0439\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0432 \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u0442\u043e\u0440\u0435\u043d\u0438\u044f, \u0432\u0441\u0435-\u0440\u0430\u0432\u043d\u043e \u043d\u0430 \u043d\u0438\u0445 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043a\u0443\u043f\u0438\u0448\u044c.\" data-title=\"&lt;p> \u041d\u0443 \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0432\u0441\u0435 \u0446\u0435\u043d\u044b \u0443\u043a\u0430\u0437\u0430\u043d\u044b \u043d\u0435 \u0432 \u0435\u0434\u0438\u043d\u0438\u0446\u0430\u0445 \u0434\u0435\u043d\u0435\u0433, \u0430 \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043c\u043e\u043d\u0435\u0442 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u043e\u043c. \u0411\u044e\u0434\u0436\u0435\u0442 \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u044d\u0442\u0438\u0445 \u043c\u043e\u043d\u0435\u0442\u0430\u0445, \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043a\u043e\u043f\u0435\u0439\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0432 \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u0442\u043e\u0440\u0435\u043d\u0438\u044f, \u0432\u0441\u0435-\u0440\u0430\u0432\u043d\u043e \u043d\u0430 \u043d\u0438\u0445 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043a\u0443\u043f\u0438\u0448\u044c. &lt;\/p>&#187; data-abbr=&#187;\u043c\u043e\u0436\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr> \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u0441\u0435 \u0442\u0440\u0438 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c (\u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 <code>c<\/code>, \u0442\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430\u0446\u0435\u043b\u043e). \u041f\u0443\u0441\u0442\u044c <code>x<\/code> \u0438 <code>y<\/code> &#8212; \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0438 \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u043c\u044b \u043f\u043e\u043a\u0443\u043f\u0430\u0435\u043c. \u0422\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0414\u0438\u043e\u0444\u0430\u043d\u0442\u043e\u0432\u043e \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"ax+by \\le c, x \\ge 0, y \\ge 0\" alt=\"ax+by \\le c, x \\ge 0, y \\ge 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4ec\/bf5\/cf1\/4ecbf5cf190cc3a6affe5f1e680c3c5b.svg\" width=\"205\" height=\"20\"\/><\/p>\n<p>\u041d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0430 \u0441 \u0434\u0432\u0443\u043c\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u043c\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0432\u043e\u043e\u0431\u0449\u0435 \u0441\u043b\u043e\u0436\u043d\u043e. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043a\u0430\u043a-\u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0434\u043d\u0443 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e. \u042d\u0442\u0430\u043b\u043e\u043d\u043d\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <code>x<\/code> \u0438 \u0434\u0430\u043b\u044c\u0448\u0435 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <code>y<\/code>. \u041d\u043e \u043a\u0430\u043a \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0443\u0441\u043a\u043e\u0440\u044f\u0442\u044c \u044f \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u043c\u0435\u0441\u0442\u043e \u044d\u0442\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u043f\u043e\u0442\u0440\u0430\u0447\u0435\u043d\u043d\u0443\u044e \u0441\u0443\u043c\u043c\u0443:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"ax+by = i, x \\ge 0, y \\ge 0, 0 \\le i \\le c\" alt=\"ax+by = i, x \\ge 0, y \\ge 0, 0 \\le i \\le c\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/42e\/f7d\/b6e\/42ef7db6e1c0c94d59e79e9ea2ac5789.svg\" width=\"288\" height=\"20\"\/><\/p>\n<p>\u042d\u0442\u043e \u0443\u0436\u0435 \u0414\u0438\u0430\u0444\u0430\u043d\u0442\u043e\u0432\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u043a\u0430\u043a\u0438\u043c\u0438-\u0442\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c\u0438. \u041d\u043e \u043e\u043d\u043e \u0432\u0435\u0441\u044c\u043c\u0430 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0435 \u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043c\u044b \u0443\u0436\u0435 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u043b\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043e\u0431\u0449\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0439:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x = x_0i+bt \\\\ y=y_0i-at \\\\ x_0a+y_0b = 1\" alt=\"x = x_0i+bt \\\\ y=y_0i-at \\\\ x_0a+y_0b = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/275\/3c0\/6fa\/2753c06fae4d5d0d53aa34774e3be03d.svg\" width=\"698\" height=\"70\"\/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_0\" alt=\"x_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9dc\/c3d\/243\/9dcc3d2439be40c3dc4a40827a1b1db4.svg\" width=\"20\" height=\"15\"\/>\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"y_0\" alt=\"y_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/535\/73d\/e93\/53573de93e4f82b6b977119703ed02c7.svg\" width=\"18\" height=\"15\"\/>\u0442\u0443\u0442 &#8212; \u044d\u0442\u043e \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0447\u0435\u0440\u0435\u0437 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A0%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u044d\u0432\u043a\u043b\u0438\u0434\u0430<\/a>. <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d19\/94a\/b57\/d1994ab571571733ddc27df02195fc87.svg\" width=\"7\" height=\"16\"\/>&#8212; \u044d\u0442\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0430\u044f \u043f\u0440\u044b\u0433\u0430\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0439. \u0421\u0434\u0432\u0438\u0433\u0438 \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{b, -a\\}\" alt=\"\\{b, -a\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d40\/1a6\/d74\/d401a6d747e268a0a27a347c366873b1.svg\" width=\"61\" height=\"22\"\/>\u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 <abbr class=\"habraabbr\" title=\"\u0412\u043e\u043e\u0431\u0449\u0435, \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0439 (\u0434\u0430\u0436\u0435 \u043d\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435) \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u0434\u0440\u0443\u0433 \u0438\u0437 \u0434\u0440\u0443\u0433\u0430 \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440. \u041d\u043e \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 GCD(a,b)=1, \u0442\u043e \u044d\u0442\u043e \u0441\u0430\u043c\u044b\u0439 \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u043a\u043e\u043b\u043b\u0438\u043d\u0435\u0430\u0440\u043d\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0439.\" data-title=\"&lt;p>\u0412\u043e\u043e\u0431\u0449\u0435, \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0439 (\u0434\u0430\u0436\u0435 \u043d\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435) \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u0434\u0440\u0443\u0433 \u0438\u0437 \u0434\u0440\u0443\u0433\u0430 \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440. \u041d\u043e \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 GCD(a,b)=1, \u0442\u043e \u044d\u0442\u043e \u0441\u0430\u043c\u044b\u0439 \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u043a\u043e\u043b\u043b\u0438\u043d\u0435\u0430\u0440\u043d\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0439.&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b<\/abbr>. <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x\" alt=\"x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1c4\/8c4\/354\/1c48c4354443ae1d8fd683ef38be3ed2.svg\" width=\"11\" height=\"12\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"y\" alt=\"y\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1e8\/07d\/bcb\/1e807dbcb9070a146b972e0aebc3f9a3.svg\" width=\"10\" height=\"15\"\/>. \u041e\u043d\u0438 \u0434\u0430\u044e\u0442 \u043d\u0430\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/09b\/2ac\/b60\/09b2acb60e6ab7c386c7c6bdbb1e0c27.svg\" width=\"7\" height=\"16\"\/>:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\frac{-x_0 i}{b} \\leq t \\leq \\frac{y_0 i}{a} \" alt=\"\\frac{-x_0 i}{b} \\leq t \\leq \\frac{y_0 i}{a} \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ec2\/6b1\/bd8\/ec26b1bd833dec7654b20bab9cb79bd5.svg\" width=\"139\" height=\"42\"\/><\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/98f\/65f\/209\/98f65f209892d33269339bdaac965040.svg\" width=\"7\" height=\"16\"\/>\u0446\u0435\u043b\u043e\u0435, \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\lceil \\frac{-x_0 i}{b}\\rceil \\leq t  \\leq \\lfloor \\frac{y_0 i}{a} \\rfloor\" alt=\"\\lceil \\frac{-x_0 i}{b}\\rceil \\leq t  \\leq \\lfloor \\frac{y_0 i}{a} \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/372\/e4f\/dba\/372e4fdba81eaa2731481bf84fc738c3.svg\" width=\"173\" height=\"42\"\/><\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0435 \u0434\u0443\u043c\u0430\u0442\u044c \u043e\u0431 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430\u0445, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0434\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c\u0441\u044f, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_0 \\leq 0\" alt=\"x_0 \\leq 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ca4\/474\/92b\/ca447492bbaaa91e20803e27ab4aa6e8.svg\" width=\"55\" height=\"19\"\/>, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"y_0 \\geq 0\" alt=\"y_0 \\geq 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2e7\/791\/9dd\/2e77919ddb9d100a47f35e483f52ce17.svg\" width=\"54\" height=\"19\"\/>. \u042d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e <abbr class=\"habraabbr\" title=\"\u0415\u0441\u043b\u0438 x0 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440 {-b, a} \u043a\u0443\u0447\u0443 \u0440\u0430\u0437. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e y0 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0436\u0435 \u0432\u0435\u043a\u0442\u043e\u0440 \u0435\u0449\u0435 \u043a\u0443\u0447\u0443 \u0440\u0430\u0437.\" data-title=\"&lt;p>\u0415\u0441\u043b\u0438 x0 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440 {-b, a} \u043a\u0443\u0447\u0443 \u0440\u0430\u0437. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e y0 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0436\u0435 \u0432\u0435\u043a\u0442\u043e\u0440 \u0435\u0449\u0435 \u043a\u0443\u0447\u0443 \u0440\u0430\u0437.&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr> \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f. \u0422\u0443\u0442 \u0436\u0435 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e <abbr class=\"habraabbr\" title=\"\u041f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0438\u0432 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0432 \u044d\u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 (\u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e x0 \u0438 y0) \u043f\u043e\u043b\u0443\u0447\u0438\u043c 0 \u043c\u0435\u043d\u044c\u0448\u0435 i\" data-title=\"&lt;p>\u041f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0438\u0432 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0432 \u044d\u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 (\u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e x0 \u0438 y0) \u043f\u043e\u043b\u0443\u0447\u0438\u043c 0 \u043c\u0435\u043d\u044c\u0448\u0435 i&lt;\/p>&lt;p>&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e &#171;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e <\/abbr><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\" \\frac{-x_0i}{b} \\le \\frac{y_0i}{a}\" alt=\" \\frac{-x_0i}{b} \\le \\frac{y_0i}{a}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ad1\/aa9\/5d2\/ad1aa95d20e9c8a9313336641ac7c1f5.svg\" width=\"106\" height=\"42\"\/>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443, \u043e\u043a\u0440\u0443\u0433\u043b\u044f\u044f \u044d\u0442\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432\u0432\u0435\u0440\u0445 \u0438 \u0432\u043d\u0438\u0437 \u043c\u044b \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043d\u0438\u0436\u043d\u044e\u044e \u0433\u0440\u0430\u043d\u0438\u0446\u0443 \u043d\u0430 1 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0435\u0440\u0445\u043d\u0435\u0439 \u0433\u0440\u0430\u043d\u0438\u0446\u044b (\u0435\u0441\u043b\u0438 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u043e\u043a\u0430\u0437\u0430\u043b\u0438\u0441\u044c \u043c\u0435\u0436\u0434\u0443 \u043e\u0434\u043d\u0438\u043c\u0438 \u0438 \u0442\u0435\u043c\u0438 \u0436\u0435 \u0446\u0435\u043b\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438). \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0435\u043b\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 t, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0435 \u0432\u0441\u0435\u043c \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0430\u043c (\u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u0438\u0445 \u0442\u0430\u043c \u0442\u0430\u043a\u0438\u0445 \u043d\u0435\u0442), \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0430\u043a: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lfloor \\frac{y_0 i}{a} \\rfloor - \\lceil \\frac{-x_0 i}{b}\\rceil +1\" alt=\"\\lfloor \\frac{y_0 i}{a} \\rfloor - \\lceil \\frac{-x_0 i}{b}\\rceil +1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8a5\/eda\/492\/8a5eda4923f68ec18780d1ab886e8b63.svg\" width=\"171\" height=\"42\"\/><\/p>\n<p>\u0410 \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/00f\/933\/189\/00f9331890d5f533fa3af94cae4289e0.svg\" width=\"7\" height=\"16\"\/> \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e <code>c<\/code>, \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0434\u043b\u044f \u043e\u0442\u0432\u0435\u0442\u0430 \u0431\u0443\u0434\u0435\u0442:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=0}^c \\left(\\lfloor \\frac{y_0 i}{a} \\rfloor - \\lceil \\frac{-x_0 i}{b}\\rceil +1\\right) \" alt=\"\\sum_{i=0}^c \\left(\\lfloor \\frac{y_0 i}{a} \\rfloor - \\lceil \\frac{-x_0 i}{b}\\rceil +1\\right) \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7f8\/25f\/952\/7f825f952138ef376d2694eddcf00f61.svg\" width=\"231\" height=\"57\"\/><\/p>\n<p>\u0422\u0443\u0442 \u0432 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u043a\u0443 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f \u0432\u043d\u0438\u0437 \u0438 \u0432\u0432\u0435\u0440\u0445. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u044b\u0440\u0430\u0437\u0438\u043c ceil \u0447\u0435\u0440\u0435\u0437 floor. \u041e\u043d\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043d\u0430 1, \u043a\u0440\u043e\u043c\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u043a\u043e\u0433\u0434\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e\u0434 ceil \u0446\u0435\u043b\u043e\u0435. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_0\" alt=\"x_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/471\/089\/a2a\/471089a2ab27aca3b424a6213b057c78.svg\" width=\"20\" height=\"15\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"b\" alt=\"b\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ab2\/e5a\/c96\/ab2e5ac9646f0e41834792cb86631e54.svg\" width=\"8\" height=\"17\"\/> <abbr class=\"habraabbr\" title=\"\u0415\u0441\u043b\u0438 \u0431\u044b \u0443 \u043d\u0438\u0445 \u0431\u044b\u043b \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u0432\u0430\u0440\u0430\u0436\u0435\u043d\u0438\u0435 x0a+y0b \u043d\u0430 \u043d\u0435\u0433\u043e \u0431\u044b \u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c, \u0430 \u043e\u043d\u043e \u0440\u0430\u0432\u043d\u043e 1\" data-title=\"&lt;p>\u0415\u0441\u043b\u0438 \u0431\u044b \u0443 \u043d\u0438\u0445 \u0431\u044b\u043b \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u0432\u0430\u0440\u0430\u0436\u0435\u043d\u0438\u0435 x0a+y0b \u043d\u0430 \u043d\u0435\u0433\u043e \u0431\u044b \u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c, \u0430 \u043e\u043d\u043e \u0440\u0430\u0432\u043d\u043e 1&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e &#171;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e <\/abbr>\u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u043f\u043e\u0434 ceil \u0446\u0435\u043b\u043e\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/60a\/3d2\/e2d\/60a3d2e2d21e44f9ecd374eaa5c2ae7e.svg\" width=\"7\" height=\"16\"\/> \u0434\u0435\u043b\u044f\u0449\u0438\u0445\u0441\u044f \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"b\" alt=\"b\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/089\/7b3\/e08\/0897b3e087ccb231534954a4c9b56b1a.svg\" width=\"8\" height=\"17\"\/>. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0442\u0430\u043c \u0432\u0435\u0437\u0434\u0435 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c ceil=floor+1, \u043d\u043e \u0437\u0430\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0440\u043e\u0432\u043d\u043e \u0432 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lfloor\\frac{c}{b}\\rfloor+1\" alt=\"\\lfloor\\frac{c}{b}\\rfloor+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d0\/24e\/fd3\/4d024efd3799c7059a0deee522033881.svg\" width=\"66\" height=\"38\"\/>\u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f\u0445 \u0443 \u043d\u0430\u0441 \u0432\u044b\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043b\u0438\u0448\u043d\u044f\u044f \u0435\u0434\u0438\u043d\u0438\u0446\u0430, \u0438\u0445 \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u043b\u0435 \u0441\u0443\u043c\u043c\u044b \u043d\u0430\u0437\u0430\u0434 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c. +1 \u043e\u0442 ceil \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c\u0441\u044f \u0441 +1 \u0443\u0436\u0435 \u043f\u043e\u0434 \u0437\u043d\u0430\u043a\u043e\u043c \u0441\u0443\u043c\u043c\u044b \u0438 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=0}^c \\left(\\lfloor \\frac{y_0 i}{a} \\rfloor - \\lfloor \\frac{-x_0 i}{b}\\rfloor \\right) + \\lfloor \\frac{c}{b}\\rfloor +1\" alt=\"\\sum_{i=0}^c \\left(\\lfloor \\frac{y_0 i}{a} \\rfloor - \\lfloor \\frac{-x_0 i}{b}\\rfloor \\right) + \\lfloor \\frac{c}{b}\\rfloor +1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/906\/e26\/7a4\/906e267a47e9c059464cb9f085bc7fe7.svg\" width=\"287\" height=\"57\"\/><\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0430\u0437\u043e\u0431\u044c\u0435\u043c \u0441\u0443\u043c\u043c\u0443 \u043d\u0430 \u0434\u0432\u0435 \u0438 \u0432\u0432\u0435\u0434\u0435\u043c \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = \\sum_{i=0}^{n-1} \\lfloor \\frac{ki}{m}\\rfloor\" alt=\"SumFloor(n, k, m) = \\sum_{i=0}^{n-1} \\lfloor \\frac{ki}{m}\\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f2c\/1aa\/283\/f2c1aa283f216a1d2b31c552928d6b1f.svg\" width=\"253\" height=\"60\"\/><\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435, \u043e\u0442\u0432\u0435\u0442 \u043a \u0437\u0430\u0434\u0430\u0447\u0435:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(c+1, y_0, a)-SumFloor(c+1, -x_0, b)+\\lfloor\\frac{c}{b}\\rfloor+1\" alt=\"SumFloor(c+1, y_0, a)-SumFloor(c+1, -x_0, b)+\\lfloor\\frac{c}{b}\\rfloor+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/65d\/130\/fc1\/65d130fc139ac6bcf91872a43bfbe03f.svg\" width=\"508\" height=\"38\"\/><\/p>\n<h2>\u0412\u044b\u0432\u043e\u0434\u0438\u043c \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u0441\u0443\u043c\u043c\u044b<\/h2>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0441\u0442\u0430\u043b\u0430\u0441\u044c \u0441\u0430\u043c\u0430\u044f \u043c\u0430\u043b\u043e\u0441\u0442\u044c: \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0432 <code>SumFloor<\/code> \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c.<\/p>\n<h3>\u0411\u043e\u0440\u0435\u043c\u0441\u044f \u0441 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u043c\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c\u0438<\/h3>\n<p>\u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bb7\/e6f\/8ae\/bb7e6f8ae6cb3f9a570ba711c1181abe.svg\" width=\"10\" height=\"17\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/264\/bcc\/8d8\/264bcc8d8282eeb969ca6dc1d692d196.svg\" width=\"17\" height=\"12\"\/>\u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b. \u041c\u043e\u0436\u043d\u043e \u0438\u0445 \u043d\u0430 \u041d\u041e\u0414 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c, \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u0432 \u043d\u0438 \u043e\u0434\u043d\u043e \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u0435. \u041d\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u0447\u0438\u0441\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432 \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f, \u0443\u0436\u0435 \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b (\u0441\u043c. &#171;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187; \u0432\u044b\u0448\u0435). \u041d\u043e \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c GCD \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e &#8212; \u043d\u0430 \u043e\u0446\u0435\u043d\u043a\u0443 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u043e \u043d\u0435 \u043f\u043e\u0432\u043b\u0438\u044f\u0435\u0442.<\/p>\n<p>\u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k &lt; m\" alt=\"k &lt; m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8d2\/6c0\/b43\/8d26c0b431da063c8ce611912c2bc971.svg\" width=\"53\" height=\"17\"\/>. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u043b\u0438\u0448\u043d\u044e\u044e \u0447\u0430\u0441\u0442\u044c, \u0435\u0441\u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k=mf+k', k' = k\\%m&lt;m\" alt=\"k=mf+k', k' = k\\%m&lt;m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f60\/cee\/eec\/f60ceeeec38e0171df6cd25a541bc5a8.svg\" width=\"238\" height=\"22\"\/>\u0432 \u0441\u0443\u043c\u043c\u0443 \u0438 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0432\u0441\u0435 \u0446\u0435\u043b\u043e\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0432 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u0438:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\" \\sum_{i=0}^{n-1} \\lfloor \\frac{(mf+k')i}{m}\\rfloor= \\sum_{i=0}^{n-1} \\left( fi +\\lfloor \\frac{k'i}{m}\\rfloor \\right) = \\sum_{i=0}^{n-1} \\lfloor \\frac{k'i}{m}\\rfloor  + \\frac{fn(n-1)}{2}\" alt=\" \\sum_{i=0}^{n-1} \\lfloor \\frac{(mf+k')i}{m}\\rfloor= \\sum_{i=0}^{n-1} \\left( fi +\\lfloor \\frac{k'i}{m}\\rfloor \\right) = \\sum_{i=0}^{n-1} \\lfloor \\frac{k'i}{m}\\rfloor  + \\frac{fn(n-1)}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2df\/fe8\/45d\/2dffe845db8841203b3175777353f7b1.svg\" width=\"526\" height=\"60\"\/><\/p>\n<p>\u0418\u043b\u0438:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = SumFloor(n, k\\%m, m)+\\frac{\\lfloor\\frac{k}{m}\\rfloor n (n-1)}{2}\" alt=\"SumFloor(n, k, m) = SumFloor(n, k\\%m, m)+\\frac{\\lfloor\\frac{k}{m}\\rfloor n (n-1)}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d47\/32a\/885\/d4732a88507cc238e6f11d6d84bccc19.svg\" width=\"514\" height=\"50\"\/><\/p>\n<p>\u0412\u043e\u0442 \u043c\u044b \u0438 \u0432\u044b\u0440\u0430\u0437\u0438\u043b\u0438 \u0441\u0443\u043c\u043c\u0443 \u0441 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c3\/ee6\/a4b\/4c3ee6a4b2a1ca35413474ce7e36999d.svg\" width=\"10\" height=\"17\"\/>\u0447\u0435\u0440\u0435\u0437 \u0441\u0443\u043c\u043c\u0443 c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k' &lt; m\" alt=\"k' &lt; m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a7a\/650\/a5e\/a7a650a5ea557da7444dd53495b15f4e.svg\" width=\"58\" height=\"19\"\/>.<\/p>\n<p>\u0412\u043e-\u0442\u0440\u0435\u0442\u044c\u0438\u0445, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n \\le m\" alt=\"n \\le m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/14b\/f5c\/517\/14bf5c51767967724f974ff02491a839.svg\" width=\"54\" height=\"18\"\/>. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u043d\u0430 \u043a\u0443\u0441\u043a\u0438, \u043f\u0435\u0440\u0432\u044b\u0439 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043f\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/71a\/f64\/f55\/71af64f55f6ee6592e58525221d69ffe.svg\" width=\"17\" height=\"12\"\/>\u0447\u0438\u0441\u0435\u043b, \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c m. \u041f\u0443\u0441\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n = mf + n', n' = n\\%m &lt; m\" alt=\"n = mf + n', n' = n\\%m &lt; m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/699\/bc0\/102\/699bc0102e4728a53bfba33af388a3d6.svg\" width=\"244\" height=\"22\"\/>, \u0442\u043e\u0433\u0434\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = \\sum_{i=0}^{mf-1} \\lfloor \\frac{ki}{m}\\rfloor + \\sum_{i=mf}^{mf+n'-1} \\lfloor \\frac{ki}{m}\\rfloor\" alt=\"SumFloor(n, k, m) = \\sum_{i=0}^{mf-1} \\lfloor \\frac{ki}{m}\\rfloor + \\sum_{i=mf}^{mf+n'-1} \\lfloor \\frac{ki}{m}\\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/784\/88f\/c19\/78488fc19b6ac104884654f5731788a2.svg\" width=\"387\" height=\"65\"\/><\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0442\u0440\u0438\u043c \u043b\u0435\u0432\u0443\u044e \u0438 \u043f\u0440\u0430\u0432\u0443\u044e \u0441\u0443\u043c\u043c\u044b. \u0412 \u043b\u0435\u0432\u043e\u0439 \u0441\u0443\u043c\u043c\u0435 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lfloor a\/b \\rfloor = \\frac{a - a \\%b}{b}\" alt=\"\\lfloor a\/b \\rfloor = \\frac{a - a \\%b}{b}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c47\/301\/a6a\/c47301a6afdc9ebe771ca672df377ce2.svg\" width=\"146\" height=\"44\"\/>\u0438 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u043d\u0435-\u043c\u043e\u0434\u0443\u043b\u0438 \u043a\u0430\u043a \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u044e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=0}^{mf-1} \\lfloor \\frac{ki}{m}\\rfloor = \\sum_{i=0}^{mf-1}  \\frac{ki-(ki)\\%m}{m} = \\frac{kmf(mf-1)}{2m} - \\sum_{i=0}^{mf-1}  \\frac{(ki)\\%m}{m}\" alt=\"\\sum_{i=0}^{mf-1} \\lfloor \\frac{ki}{m}\\rfloor = \\sum_{i=0}^{mf-1}  \\frac{ki-(ki)\\%m}{m} = \\frac{kmf(mf-1)}{2m} - \\sum_{i=0}^{mf-1}  \\frac{(ki)\\%m}{m}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9dc\/8b3\/d06\/9dc8b3d0656ff63372ca755411561b97.svg\" width=\"537\" height=\"61\"\/><\/p>\n<p>\u0412 \u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0439\u0441\u044f \u0441\u0443\u043c\u043c\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/544\/2d5\/5f9\/5442d55f9a079f881f81c25b401df2ba.svg\" width=\"7\" height=\"16\"\/> \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/83c\/345\/795\/83c3457955ef2ce4fe2299ddd2dd93d8.svg\" width=\"17\" height=\"12\"\/> \u0440\u043e\u0432\u043d\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6c2\/584\/01b\/6c258401bf4c0d2d6045f4d2b63ee71a.svg\" width=\"11\" height=\"20\"\/> \u0440\u0430\u0437. \u0410 \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/76c\/bce\/03c\/76cbce03c12e6be35eda6a293c202f63.svg\" width=\"10\" height=\"17\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/478\/7d1\/8cb\/4787d18cbdb0063469b72bfc10a293e5.svg\" width=\"17\" height=\"12\"\/> \u0432\u0437\u0430\u0438\u043c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e <abbr class=\"habraabbr\" title=\"\u0420\u0430\u0437 k \u0438 m \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0443 k \u0435\u0441\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e m. \u0410 \u0437\u043d\u0430\u0447\u0438\u0442 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 ki%m=x \u0438\u043c\u0435\u0435\u0442 \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 x\" data-title=\"&lt;p>\u0420\u0430\u0437 k \u0438 m \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0443 k \u0435\u0441\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e m. \u0410 \u0437\u043d\u0430\u0447\u0438\u0442 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 ki%m=x \u0438\u043c\u0435\u0435\u0442 \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 x&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e &#171;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e <\/abbr><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"ki\" alt=\"ki\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/20a\/3b3\/517\/20a3b351731be8dc1e4ee5a05b4c7608.svg\" width=\"17\" height=\"17\"\/>\u0442\u043e\u0436\u0435 \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/acb\/bcc\/959\/acbbcc95994f31fad835e8f03ec436f3.svg\" width=\"17\" height=\"12\"\/> \u0440\u043e\u0432\u043d\u043e<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a0b\/c09\/f05\/a0bc09f05981435434d4055a99ef85af.svg\" width=\"11\" height=\"20\"\/>\u0440\u0430\u0437, \u043d\u043e \u0432 \u043a\u0430\u043a\u043e\u043c-\u0442\u043e \u0434\u0440\u0443\u0433\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u041d\u043e \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0430\u043c \u043d\u0435 \u0432\u0430\u0436\u0435\u043d, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0be\/72c\/64e\/0be72c64ef266153dcf83117dcbb2efc.svg\" width=\"11\" height=\"20\"\/>\u0440\u0430\u0437 \u043f\u0440\u043e\u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043e\u0442 0 \u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m-1\" alt=\"m-1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/889\/dae\/c4b\/889daec4bbec66234fe42536ac34babb.svg\" width=\"50\" height=\"17\"\/>. \u0418\u0442\u0430\u043a, \u043b\u0435\u0432\u0430\u044f \u0441\u0443\u043c\u043c\u0430 \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\frac{kmf(mf-1)}{2m} - f\\frac{m(m-1)}{2m} = \\frac{f(kmf-k-m+1)}{2}\" alt=\"\\frac{kmf(mf-1)}{2m} - f\\frac{m(m-1)}{2m} = \\frac{f(kmf-k-m+1)}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2a4\/ccd\/835\/2a4ccd83518b8df1d12f35d74f29ad86.svg\" width=\"447\" height=\"45\"\/><\/p>\n<p>\u0412 \u043f\u0440\u0430\u0432\u043e\u0439 \u0441\u0443\u043c\u043c\u0435 \u0437\u0430\u043c\u0435\u043d\u0438\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = mf+i'\" alt=\"i = mf+i'\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/11b\/426\/494\/11b426494c3a4a28a5ff25b1e6812693.svg\" width=\"96\" height=\"22\"\/>:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=mf}^{mf+n'-1} \\lfloor \\frac{ki}{m}\\rfloor = \\sum_{i'=0}^{n'-1} \\lfloor \\frac{k(mf+i')}{m}\\rfloor =  \\sum_{i'=0}^{n'-1} \\lfloor \\frac{ki'}{m}\\rfloor+kfn'\" alt=\"\\sum_{i=mf}^{mf+n'-1} \\lfloor \\frac{ki}{m}\\rfloor = \\sum_{i'=0}^{n'-1} \\lfloor \\frac{k(mf+i')}{m}\\rfloor =  \\sum_{i'=0}^{n'-1} \\lfloor \\frac{ki'}{m}\\rfloor+kfn'\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c7f\/4aa\/405\/c7f4aa4052b507ccfd5a47e2417947ea.svg\" width=\"432\" height=\"65\"\/><\/p>\n<p>\u0421\u043e\u0431\u0438\u0440\u0430\u044f \u0432\u0441\u0435 \u0432\u043c\u0435\u0441\u0442\u0435, \u043f\u043e\u043c\u043d\u044f, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f = \\lfloor \\frac{n}{m} \\rfloor\" alt=\"f = \\lfloor \\frac{n}{m} \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/abc\/d29\/0c7\/abcd290c76bd093ff6a1a9fec6adf4f2.svg\" width=\"77\" height=\"38\"\/>:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = SumFloor(n\\%m, k, m) + \\frac{f(kmf-k-m+1)}{2} +kf(n\\%m)\" alt=\"SumFloor(n, k, m) = SumFloor(n\\%m, k, m) + \\frac{f(kmf-k-m+1)}{2} +kf(n\\%m)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/324\/9ff\/b1e\/3249ffb1ec419834d3f3f45fe25f3fe9.svg\" width=\"681\" height=\"45\"\/><\/p>\n<p>\u0412\u043e\u0442 \u043c\u044b \u0438 \u0432\u044b\u0440\u0430\u0437\u0438\u043b\u0438 \u0441\u0443\u043c\u043c\u0443 \u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e13\/0cc\/6bb\/e130cc6bb2dc6aa1dc0225c37fd702b9.svg\" width=\"12\" height=\"12\"\/>\u0447\u0435\u0440\u0435\u0437 \u0441\u0443\u043c\u043c\u0443 \u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n' &lt; m\" alt=\"n' &lt; m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f5c\/5b2\/199\/f5c5b219966d82395369cb3405d72a9d.svg\" width=\"60\" height=\"19\"\/>.<\/p>\n<h3>\u0412\u044b\u0432\u043e\u0434\u0438\u043c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u043e\u0431\u0449\u0435\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f<\/h3>\n<p>\u0418\u0442\u0430\u043a, \u043c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"GCD(m, k) = 1\" alt=\"GCD(m, k) = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/be5\/515\/44c\/be551544c38fd91357411fc16725a2b1.svg\" width=\"132\" height=\"22\"\/>, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k &lt; m\" alt=\"k &lt; m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/861\/b33\/a2b\/861b33a2bf2a0ec9a13a047e818179cf.svg\" width=\"53\" height=\"17\"\/>, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n \\le m\" alt=\"n \\le m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ad0\/3f2\/365\/ad03f23652bbb674335d6c41072a1a28.svg\" width=\"54\" height=\"18\"\/>.<\/p>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u0433\u043b\u0430\u0432\u043d\u0430\u044f \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u044c \u0442\u0443\u0442, \u044d\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Hermite%27s_identity\" rel=\"noopener noreferrer nofollow\">Hermite&#8217;s identity<\/a>. \u042f \u043c\u043d\u043e\u0433\u043e \u0441 \u043d\u0438\u043c \u044d\u043a\u0441\u043f\u0435\u0440\u0435\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0438 \u0441\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u0437\u0430<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7df\/4ee\/18d\/7df4ee18dcc9b315a4958fa2b9d3529e.svg\" width=\"12\" height=\"12\"\/>\u0447\u0438\u0441\u043b\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b27\/046\/aae\/b27046aae6daeb439eb1a605310de509.svg\" width=\"10\" height=\"17\"\/>, \u0430 \u0437\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x\" alt=\"x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/db5\/e53\/b14\/db5e53b1457df058ee2c93b946c3a136.svg\" width=\"11\" height=\"12\"\/>\u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0435\u0441\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\frac{i}{m}\" alt=\"\\frac{i}{m}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2aa\/0e3\/1f0\/2aa0e31f0df1cc96a3505c477ff28bfa.svg\" width=\"24\" height=\"42\"\/>:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=0}^{n-1} \\lfloor \\frac{ki}{m} \\rfloor = \\sum_{i=0}^{n-1} \\sum_{t=0}^{k-1} \\lfloor \\frac{i}{m} + \\frac{t}{k} \\rfloor\" alt=\"\\sum_{i=0}^{n-1} \\lfloor \\frac{ki}{m} \\rfloor = \\sum_{i=0}^{n-1} \\sum_{t=0}^{k-1} \\lfloor \\frac{i}{m} + \\frac{t}{k} \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/37d\/85e\/330\/37d85e3301eef91aa4bb13d7c0f35da8.svg\" width=\"235\" height=\"60\"\/><\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u043e \u044d\u0442\u043e \u0431\u044b\u0432\u0430\u0435\u0442 \u0441\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u043c\u0438 \u0441\u0443\u043c\u043c\u0430\u043c\u0438, \u0438\u043d\u0442\u0435\u0433\u0440\u0430\u043b\u0430\u043c\u0438 \u0438\u043b\u0438 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u043c\u0438, \u043d\u0430\u0434\u043e \u043f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0438\u0445 \u043f\u043e\u0440\u044f\u0434\u043e\u043a:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = \\sum_{t=0}^{k-1} \\sum_{i=0}^{n-1} \\lfloor \\frac{i}{m} + \\frac{t}{k} \\rfloor\" alt=\"SumFloor(n, k, m) = \\sum_{t=0}^{k-1} \\sum_{i=0}^{n-1} \\lfloor \\frac{i}{m} + \\frac{t}{k} \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ab\/36e\/8bf\/1ab36e8bff4b4b11a00cd210b1f28458.svg\" width=\"325\" height=\"60\"\/><\/p>\n<p>\u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0434\u043e\u0433\u0430\u0434\u043a\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u043e\u0434 \u0437\u043d\u0430\u043a\u043e\u043c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f \u0432\u043d\u0438\u0437 \u0441\u0442\u043e\u0438\u0442 \u0441\u0443\u043c\u043c\u0430 \u0438\u0437 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b, \u043c\u0435\u043d\u044c\u0448\u0438\u0445 1 \u043a\u0430\u0436\u0434\u043e\u0435! \u0412\u0435\u0434\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i &lt; n \\le m\" alt=\"i &lt; n \\le m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7d9\/6d0\/2a0\/7d96d02a0cbeda5a73cf8bac935dd668.svg\" width=\"87\" height=\"18\"\/>\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t &lt; k\" alt=\"t &lt; k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e1a\/adb\/1b5\/e1aadb1b51c2e8ae692d2b4e3560d2ef.svg\" width=\"43\" height=\"17\"\/>. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 floor \u0431\u0443\u0434\u0435\u0442 \u0438\u043b\u0438 0 \u0438\u043b\u0438 1. 1 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\frac{i}{m} + \\frac{t}{k} \\ge 1\" alt=\"\\frac{i}{m} + \\frac{t}{k} \\ge 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ac\/cec\/ba9\/1accecba946c56aea7b056b21d87e604.svg\" width=\"100\" height=\"42\"\/>. \u041e\u0442\u0441\u044e\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/93c\/3f8\/463\/93c3f846394bae3b209594fb7e1fd056.svg\" width=\"7\" height=\"16\"\/>, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0447\u0442\u043e-\u0442\u043e \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0432\u043e\u043e\u0431\u0449\u0435 \u0441\u0443\u043c\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i \\ge m - \\frac{mt}{k}\" alt=\"i \\ge m - \\frac{mt}{k}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/550\/528\/14a\/55052814a85a8dfdd12935cc03b939c9.svg\" width=\"104\" height=\"42\"\/>. \u0422.\u043a. <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f9d\/0b6\/189\/f9d0b61898fef6c17229e9d19c98adb3.svg\" width=\"7\" height=\"16\"\/>\u0446\u0435\u043b\u043e\u0435, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043f\u0438\u0441\u0430\u0442\u044c:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"i \\ge m - \\lfloor\\frac{mt}{k}\\rfloor\" alt=\"i \\ge m - \\lfloor\\frac{mt}{k}\\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/85b\/515\/37b\/85b51537b5d8902474ff3e6768cdf3b1.svg\" width=\"121\" height=\"42\"\/><\/p>\n<p>\u041d\u043e \u0441\u0443\u043c\u043c\u0430 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u043f\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/042\/b17\/98b\/042b1798b77bf76f82b59896459d17cd.svg\" width=\"7\" height=\"16\"\/>\u0431\u044b\u043b\u0430 \u043e\u0442 0 \u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n-1\" alt=\"n-1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7fa\/873\/e10\/7fa873e109deed1e63d13d7c452abf1b.svg\" width=\"45\" height=\"17\"\/>\u043f\u043e\u044d\u0442\u043e\u043c\u0443, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0434\u0438\u043d\u0438\u0446\u044b, \u043d\u0430\u0434\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438\u0445 \u043e\u0442 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m - \\lfloor\\frac{mt}{k}\\rfloor\" alt=\"m - \\lfloor\\frac{mt}{k}\\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/40e\/05d\/9e7\/40e05d9e7aa1b7012cefb1d9f74cde49.svg\" width=\"89\" height=\"42\"\/>\u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/65a\/c1b\/4cd\/65ac1b4cdbe2a5d158943ee385374c66.svg\" width=\"12\" height=\"12\"\/>. \u041a\u043e\u0433\u0434\u0430 \u044d\u0442\u0430 \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/029\/07a\/d91\/02907ad91f3afee6675a72b8a6bf331a.svg\" width=\"12\" height=\"12\"\/>\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u0445 \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445 \u0431\u0443\u0434\u0435\u0442 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n - m + \\lfloor \\frac{mt}{k} \\rfloor\" alt=\"n - m + \\lfloor \\frac{mt}{k} \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/666\/2e8\/1e4\/6662e81e4a61443083bc6233b200331b.svg\" width=\"124\" height=\"42\"\/>. \u0415\u0441\u043b\u0438 \u0436\u0435 \u044d\u0442\u0430 \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b50\/c02\/0dc\/b50c020dcaff046af16dc78b91481e2b.svg\" width=\"12\" height=\"12\"\/>\u0442\u043e \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0441\u0443\u043c\u043c\u0435 \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442, \u043d\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0432\u044b\u0448\u0435 \u0434\u0430\u0441\u0442 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044d\u0442\u0443 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c, \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0433\u0434\u0430 \u043e\u043d\u0430 \u0434\u0430\u0435\u0442 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bcc\/d48\/5d5\/bccd485d5a162980904b761718bcfcde.svg\" width=\"7\" height=\"16\"\/>, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u044d\u0442\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"m - \\lfloor \\frac{mt}{k} \\rfloor \\le n\" alt=\"m - \\lfloor \\frac{mt}{k} \\rfloor \\le n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d9e\/174\/657\/d9e174657efa497884baef0b073a0cfb.svg\" width=\"126\" height=\"42\"\/><\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0441\u0433\u0440\u0443\u043f\u0438\u0440\u043e\u0432\u0430\u0442\u044c floor \u0438 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u043f\u043e \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0442\u043e\u0440\u043e\u043d\u044b. \u0414\u0430\u043b\u044c\u0448\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u043e \u0432\u0438\u0434\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\lfloor x \\rfloor \\ge n\" alt=\"\\lfloor x \\rfloor \\ge n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1f2\/d1e\/2d8\/1f2d1e2d8f5751381a80601b1943bef0.svg\" width=\"65\" height=\"22\"\/>\u0415\u0433\u043e \u043c\u043e\u0436\u043d\u043e <abbr class=\"habraabbr\" title=\"\u0412\u0435\u0434\u044c \u0435\u0441\u043b\u0438 x \u043c\u0435\u043d\u044c\u0448\u0435 N, \u0442\u043e \u0438 floor(x) \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435. \u0410 \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 floor  \u0446\u0435\u043b\u043e\u0435 N \u043d\u0435 \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a.\" data-title=\"&lt;p>\u0412\u0435\u0434\u044c \u0435\u0441\u043b\u0438 x \u043c\u0435\u043d\u044c\u0448\u0435 N, \u0442\u043e \u0438 floor(x) \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435. \u0410 \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 floor  \u0446\u0435\u043b\u043e\u0435 N \u043d\u0435 \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a.&lt;\/p>&lt;p>&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr> \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x \\ge n\" alt=\"x \\ge n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2fc\/922\/7e1\/2fc9227e173bf780071cd55a7650a6d1.svg\" width=\"48\" height=\"18\"\/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\frac{mt}{k} \\ge m-n\" alt=\"\\frac{mt}{k} \\ge m-n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/490\/3e7\/944\/4903e79440fd0b35affa3a7596432c70.svg\" width=\"109\" height=\"42\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"t \\ge \\frac{k(m-n)}{m}\" alt=\"t \\ge \\frac{k(m-n)}{m}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7e7\/8cd\/d48\/7e78cdd489f3414d5aaae3f7e3571109.svg\" width=\"117\" height=\"45\"\/><\/p>\n<p>\u0422.\u043a. <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7ce\/6f2\/3b2\/7ce6f23b2d2e6c99cf31c4938ae70d16.svg\" width=\"7\" height=\"16\"\/>\u0446\u0435\u043b\u043e\u0435:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"t \\ge \\lceil \\frac{k(m-n)}{m} \\rceil\" alt=\"t \\ge \\lceil \\frac{k(m-n)}{m} \\rceil\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b1b\/590\/844\/b1b590844fe8513b0e395bf1d9743dc4.svg\" width=\"134\" height=\"45\"\/><\/p>\n<p>\u042d\u0442\u043e \u0447\u0438\u0441\u043b\u043e, \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u0432\u044b\u043a\u043b\u0430\u0434\u043e\u043a \u043d\u0438\u0436\u0435, \u043d\u0430\u0437\u043e\u0432\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N' = \\lceil \\frac{k(m-n)}{m} \\rceil\" alt=\"N' = \\lceil \\frac{k(m-n)}{m} \\rceil\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/634\/ce3\/8a9\/634ce38a9893e0b7a12d800362a9d64f.svg\" width=\"150\" height=\"45\"\/>.<\/p>\n<p>\u0418\u0442\u0430\u043a, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"t\" alt=\"t\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ea9\/847\/4ff\/ea98474ff7bb443a24bc95a392156ed4.svg\" width=\"7\" height=\"16\"\/>\u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0442 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N'\" alt=\"N'\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b87\/705\/ab0\/b87705ab0952fbd1dc88b2bf870ad09d.svg\" width=\"23\" height=\"19\"\/>\u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k-1\" alt=\"k-1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e6d\/6b9\/1ce\/e6d6b91ce20f2503c0f223bd7ef8b4b3.svg\" width=\"43\" height=\"18\"\/>, \u0430 \u0432\u043d\u0443\u0442\u0440\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0441\u0443\u043c\u043c\u0430 \u0441\u043a\u043e\u043b\u044c\u043a\u0438-\u0442\u043e \u0435\u0434\u0438\u043d\u0438\u0446. \u0418\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u044b \u0443\u0436\u0435 \u0441\u0447\u0438\u0442\u0430\u043b\u0438 \u0432\u044b\u0448\u0435. \u0418\u0442\u043e\u0433\u043e\u0432\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = \\sum_{t=N'}^{k-1} \\left( n - m + \\lfloor \\frac{mt}{k} \\rfloor \\right)\" alt=\"SumFloor(n, k, m) = \\sum_{t=N'}^{k-1} \\left( n - m + \\lfloor \\frac{mt}{k} \\rfloor \\right)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e83\/2c7\/9d4\/e832c79d4d37c8612f0b4ae47fe4545d.svg\" width=\"372\" height=\"62\"\/><\/p>\n<p>\u041f\u043e\u043b\u0435\u0437\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N' \\le k\" alt=\"N' \\le k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/790\/c27\/412\/790c2741296178315dd281692dfb90a6.svg\" width=\"59\" height=\"21\"\/>(<abbr class=\"habraabbr\" title=\"\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0435, \u0442.\u043a. \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432\u0432\u0435\u0440\u0445 \u0441\u0442\u043e\u0438\u0442 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0437\u043d\u0430\u043a\u0430 \u043c\u0435\u043d\u044c\u0448\u0435. \u041f\u043e\u0442\u043e\u043c \u0432\u0441\u0435 \u0443\u043f\u0440\u043e\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430.\" data-title=\"&lt;p>\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0435, \u0442.\u043a. \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432\u0432\u0435\u0440\u0445 \u0441\u0442\u043e\u0438\u0442 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0437\u043d\u0430\u043a\u0430 \u043c\u0435\u043d\u044c\u0448\u0435. \u041f\u043e\u0442\u043e\u043c \u0432\u0441\u0435 \u0443\u043f\u0440\u043e\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430.&lt;\/p>&lt;p>&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr>), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u0430\u043f\u0438\u0441\u044c \u0432\u044b\u0448\u0435 \u0438\u043c\u0435\u0435\u0442 \u0441\u043c\u044b\u0441\u043b. \u041d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043f\u043e\u0440\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441, \u0430 \u0447\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442, \u0435\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N' = k\" alt=\"N' = k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ad1\/bd8\/125\/ad1bd8125d70c99c961888d969b246c8.svg\" width=\"59\" height=\"19\"\/>, \u043d\u043e \u044d\u0442\u043e\u0442 \u0441\u043b\u0443\u0447\u0430\u0439 \u043d\u0430\u043c \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0434\u0430\u043b\u044c\u0448\u0435 \u0438 \u0432 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c, \u0447\u0442\u043e \u0441\u0443\u043c\u043c\u0430 0 \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445 \u0440\u0430\u0432\u043d\u0430 0.<\/p>\n<p>\u0426\u0435\u043b\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u043d\u0435\u0441\u0442\u0438 \u0437\u0430 \u0437\u043d\u0430\u043a \u0441\u0443\u043c\u043c\u044b, \u043f\u043e\u043b\u0443\u0447\u0438\u0432 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(n-m)(k-N')\" alt=\"(n-m)(k-N')\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ae6\/c26\/8c2\/ae6c268c232e0a422b68bd7cceaa9151.svg\" width=\"139\" height=\"23\"\/>(\u0438 \u0434\u0430\u0436\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N'=k\" alt=\"N'=k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/141\/824\/754\/1418247548b430457c2b649daae74c45.svg\" width=\"59\" height=\"19\"\/> \u0432\u0441\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442). \u041e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 SumFloor(*, m, k), \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043e\u0442 \u0442\u0430\u043c \u0441\u0443\u043c\u043c\u0430 \u043d\u0435 \u043e\u0442 0 \u0434\u043e \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0447\u0438\u0441\u043b\u0430, \u0430 \u043e\u0442 N&#8217; \u0434\u043e \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u042d\u0442\u0443 \u0441\u0443\u043c\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c, \u043a\u0430\u043a <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"SumFloor(k, m, k) - SumFloor(N', m, k)\" alt=\"SumFloor(k, m, k) - SumFloor(N', m, k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/04c\/39e\/721\/04c39e7213605f34c0b4515a0bcf9d29.svg\" width=\"351\" height=\"23\"\/>. <\/p>\n<p>\u041f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0439 \u0438\u0442\u043e\u0433:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = (n-m)(k-N')+SumFloor(k, m, k) - SumFloor(N', m, k)\" alt=\"SumFloor(n, k, m) = (n-m)(k-N')+SumFloor(k, m, k) - SumFloor(N', m, k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d92\/152\/248\/d92152248f500f2a4a66af739ab3d310.svg\" width=\"698\" height=\"23\"\/><\/p>\n<p>\u0414\u0430\u043b\u0435\u0435, \u0432\u0441\u043f\u043e\u043c\u0438\u043d\u0430\u044f, \u043a\u0430\u043a \u043c\u044b \u0431\u043e\u0440\u043e\u043b\u0438\u0441\u044c \u0441 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u043c\u0438 \u0441\u043b\u0443\u0447\u0430\u044f\u043c\u0438, \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0443\u043c\u043c\u0430 \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e:<\/p>\n<p> <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"SumFloor(k, m, k) = SumFloor(0, m, k) + \\frac{(k-1)(m-1)}{2} = \\frac{(k-1)(m-1)}{2}\" alt=\"SumFloor(k, m, k) = SumFloor(0, m, k) + \\frac{(k-1)(m-1)}{2} = \\frac{(k-1)(m-1)}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/000\/16e\/cef\/00016ecef083d8ce8fa44e9fb3a59080.svg\" width=\"650\" height=\"45\"\/><\/p>\n<p>\u0410 \u0432\u0442\u043e\u0440\u0430\u044f \u0434\u043e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(N', m, k) = SumFloor(N', m \\% k, k) + \\frac{\\lfloor\\frac{m}{k}\\rfloor N' (N'-1)}{2}\" alt=\"SumFloor(N', m, k) = SumFloor(N', m \\% k, k) + \\frac{\\lfloor\\frac{m}{k}\\rfloor N' (N'-1)}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3d0\/6d1\/e3a\/3d06d1e3a8130242f640a7a3a2b5bf20.svg\" width=\"554\" height=\"48\"\/><\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c (\u043d\u0430\u043f\u043e\u043c\u043d\u0438\u0430\u044e, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N' = \\lceil \\frac{k(m-n)}{m} \\rceil\" alt=\"N' = \\lceil \\frac{k(m-n)}{m} \\rceil\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/805\/ba2\/1f6\/805ba21f6a44e7946e640a6f3ef1917b.svg\" width=\"150\" height=\"45\"\/>)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"SumFloor(n, k, m) = \\frac{(k-1)(m-1) - \\lfloor\\frac{m}{k}\\rfloor N' (N'-1)}{2} + (m-n)(k-N') - \\\\ - SumFloor(N', m \\% k, k)\" alt=\"SumFloor(n, k, m) = \\frac{(k-1)(m-1) - \\lfloor\\frac{m}{k}\\rfloor N' (N'-1)}{2} + (m-n)(k-N') - \\\\ - SumFloor(N', m \\% k, k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/72e\/ff3\/dc0\/72eff3dc0d183c7f5a92c76a1bb96173.svg\" width=\"698\" height=\"76\"\/><\/p>\n<p>\u041f\u0440\u0438 \u044d\u0442\u043e\u043c, \u0432\u044b\u0448\u0435 \u043c\u044b \u0443\u0436\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0438, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"N' \\le k\" alt=\"N' \\le k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dc7\/c3e\/3b7\/dc7c3e3b7db54ffbe828a76bcb284037.svg\" width=\"59\" height=\"21\"\/>. \u0422\u0430\u043a\u0436\u0435, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\\%k &lt; k\" alt=\"m\\%k &lt; k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/274\/95d\/eab\/27495deab8e1d719fa3941d494fa0c00.svg\" width=\"79\" height=\"19\"\/>. \u0422\u0430\u043a\u0436\u0435, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\\%k\" alt=\"m\\%k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4fe\/cf4\/5da\/4fecf45da04cad36ebc71770d64e8d1f.svg\" width=\"43\" height=\"19\"\/>\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/546\/ce0\/3f7\/546ce03f7f028d54a8f36ff51ecc1527.svg\" width=\"10\" height=\"17\"\/>\u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b. \u041f\u043e\u044d\u0442\u043e\u043c\u0443, \u043f\u043e\u0441\u043b\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043c\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u0441\u0442\u0430\u043d\u0435\u043c\u0441\u044f \u0432 \u0442\u043e\u043c \u0436\u0435 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043f\u044f\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043d\u0435 \u043d\u0430\u0434\u043e.<\/p>\n<p>\u0410 \u0431\u0430\u0437\u0430 \u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438, \u0435\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k=0\" alt=\"k=0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/626\/054\/fd5\/626054fd505dc30f881c1928e9cfdc34.svg\" width=\"45\" height=\"17\"\/>, \u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 0. \u0415\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m=1\" alt=\"m=1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f38\/38d\/84d\/f3838d84dc2f0342a5b58665b086cf38.svg\" width=\"52\" height=\"16\"\/>\u0438 \u0432\u044b\u0434\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"ik\" alt=\"ik\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c93\/892\/690\/c93892690ea973dc42b952974d346a66.svg\" width=\"17\" height=\"17\"\/>. \u0418\u043b\u0438, \u0435\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n=0\" alt=\"n=0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2cb\/f51\/246\/2cbf5124621b99e313d021330e809bfb.svg\" width=\"47\" height=\"16\"\/>, \u0442\u043e \u0441\u0443\u043c\u043c\u0430 \u043d\u0438\u0447\u0435\u0433\u043e &#8212; \u043d\u043e\u043b\u044c.<\/p>\n<p>\u041f\u043e\u0434\u043e\u0431\u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u042d\u0432\u043a\u043b\u0438\u0434\u0430 \u0434\u043b\u044f GCD, \u044d\u0442\u0430 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0437\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(log(max(k,m)))\" alt=\"O(log(max(k,m)))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/615\/e4b\/1fa\/615e4b1fa2040d16c1cdd545d9e620ce.svg\" width=\"158\" height=\"22\"\/>. \u0415\u0433\u043e \u0435\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7e3\/741\/503\/7e37415033bedf7963b6e22c82aa161c.svg\" width=\"39\" height=\"22\"\/>\u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0438 \u043a\u043e\u0434:<\/p>\n<pre><code class=\"cpp\">\/\/ \u0420\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u042d\u0432\u043a\u043b\u0438\u0434\u0430 \/\/ \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 GCD(a,b) \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 x, y, \u0442.\u0447. a*x+b*y=GCD(a,b) int GcdEx(int a, int b, int &amp;x, int &amp;y) {     if (b == 0) {         x = 1;         y = 0;         return a;     }     if (b > a) return GcdEx(b, a, y, x);     int xx, yy;     int d = GcdEx(b, a % b, xx, yy);     y = xx - a\/b*yy;     x = yy;     return d; }  \/\/ \u0421\u0447\u0438\u0442\u0430\u0435\u0442 sum i=0.. n-1 floor(i*k\/m) \/\/ \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f: \/\/ m > 0, 0 &lt;= k &lt; m, 0 &lt;= n &lt;= m, GCD(k, m) = 1 long long FloorSumInternal(long long n, long long k, long long m) { if (k == 0 || n == 0) return 0; if (m == 1) return k*n*(n-1)\/2; const long long n1 = ((m-n)*k + m - 1)\/m; long long ans = ((m-1)*(k-1) - (n1-1)*n1*(m\/k))\/2 + (n-m)*(k-n1); ans -=  FloorSumInternal(n1, m%k, k); return ans; }  \/\/ \u0421\u0447\u0438\u0442\u0430\u0435\u0442 sum i=0.. n-1 floor(i*k\/m) \/\/ \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0435: m > 0, k >= 0, n >= 0 long long FloorSum(long long n, long long k, long long m) { if (k == 0 || n == 0) return 0;  \/*     \u0412 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u0434\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c GCD.      \u041d\u043e \u0432 \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 k \u0438 m, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0431\u0443\u0434\u0443\u0442 \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b. const long long d = Gcd(m, k); m \/= d; k \/= d; *\/  if (m == 1) return k*n*(n-1)\/2;  if (k >= m) { return FloorSum(n, k%m, m) + (k\/m)*n*(n-1)\/2; }  if (n >= m) { long long f = n\/m; return FloorSum(n%m, k, m) + f*(k*m*f-k-m+1) \/ 2 + k*f*(n%m); }  return FloorSumInternal(n, k, m); }  \/\/ \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441\u0430\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. long long waysToBuyPensPencils(int total, int cost1, int cost2) { int x0, y0; int d = GcdEx(cost1, cost2, x0, y0); cost1 \/= d; cost2 \/= d; total \/= d;  if (x0 >= 0) { int t = x0\/cost2 + 1; x0 -= cost2*t; y0 += cost1*t; } if (y0 &lt;= 0) { int t = -y0 \/ cost1 + 1; x0 -= cost2*t; y0 += cost1*t; }  return FloorSum(total+1, y0, cost1) - FloorSum(total+1, -x0, cost2) + total \/ cost2 + 1; }<\/code><\/pre>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p> <!----> <!----><\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/746774\/\"> https:\/\/habr.com\/ru\/articles\/746774\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0415\u0441\u0442\u044c \u0432\u043e\u0442 \u0442\u0430\u043a\u0430\u044f, \u0432\u0440\u043e\u0434\u0435 \u0431\u044b, \u043f\u0440\u043e\u0441\u0442\u0430\u044f <a href=\"https:\/\/leetcode.com\/problems\/number-of-ways-to-buy-pens-and-pencils\/description\/\" rel=\"noopener noreferrer nofollow\">\u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430 \u043b\u0438\u0442\u043a\u043e\u0434\u0435<\/a>: \u0414\u0430\u043d\u043e \u0442\u0440\u0438 \u0447\u0438\u0441\u043b\u0430 <code>total<\/code> &#8212; \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0443 \u0432\u0430\u0441 \u0435\u0441\u0442\u044c \u0434\u0435\u043d\u0435\u0433, <code>cost1<\/code>, <code>cost2<\/code> &#8212; \u0446\u0435\u043d\u044b \u0434\u0432\u0443\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432. \u041d\u0430\u0434\u043e \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u0435\u0433\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u043a\u0443\u043f\u0438\u0442\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e-\u0442\u043e \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u0442\u043e\u0432\u0430\u0440\u043e\u0432, \u043d\u0435 \u0432\u044b\u0445\u043e\u0434\u044f \u0438\u0437 \u0431\u044e\u0434\u0436\u0435\u0442\u0430 (\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u043c\u0435\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u043a\u0443\u043f\u043e\u043a, \u0430 \u043d\u0435 \u043f\u043e\u0440\u044f\u0434\u043e\u043a). \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u0442 \u0446\u0435\u043b\u044b\u0445 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u0430\u0440 (x, y), \u0442\u0430\u043a\u0438\u0445 \u0447\u0442\u043e <code>x*cost1+y*cost2 &lt;= total<\/code> . \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0438\u043c\u0435\u044f \u0442\u043e\u0432\u0430\u0440\u044b \u0446\u0435\u043d\u0430\u043c\u0438 {5, 10} \u0438 20 \u0434\u0435\u043d\u0435\u0433 \u043d\u0430 \u0440\u0443\u043a\u0430\u0445, \u0435\u0441\u0442\u044c 9 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0434\u0435\u043d\u044c\u0433\u0438: 0, 5, 5+5, 5+5+5, 5+5+5+5, 10, 10+5, 10+5+5, 10+10.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0434\u0430\u0436\u0435 \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u0430 \u043a\u0430\u043a medium, \u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u043e\u0447\u0442\u0438 \u0432 \u043e\u0434\u043d\u0443 \u0441\u0442\u0440\u043e\u0447\u043a\u0443 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f, \u043d\u043e \u044d\u0442\u043e \u0435\u0441\u043b\u0438 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0431\u0435\u0437\u0443\u043c\u043d\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430 <code>O(min(cost1, cost2))<\/code>, \u0442.\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043e\u0442 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u0410 \u0441\u043c\u043e\u0436\u0435\u0442\u0435 \u043b\u0438 \u0432\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u0435\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 &#8212; \u0437\u0430 <code>O(log(max(cost1, cost2)))<\/code> ? \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0437\u0430\u0434\u0430\u0447\u043a\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0432\u043f\u043e\u043b\u043d\u0435 \u0441\u0435\u0431\u0435 hard \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438, \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438 \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e\u0441\u0442\u0438. \u0415\u0441\u043b\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0434\u043e\u0431\u0440\u043e \u043f\u043e\u0436\u0430\u043b\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0434 \u043a\u0430\u0442. \u0411\u0443\u0434\u0443 \u0440\u0430\u0434 \u043b\u044e\u0431\u044b\u043c \u0430\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u043d\u044b\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c. \u041c\u043e\u0436\u0435\u0442 \u043a\u0442\u043e-\u0442\u043e \u0441\u043c\u043e\u0436\u0435\u0442 \u0434\u043e\u0434\u0443\u043c\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u043f\u043e\u0445\u043e\u0436\u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0449\u0435.<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435 \u043f\u043e \u043e\u0444\u043e\u0440\u043c\u043b\u0435\u043d\u0438\u044e<\/summary>\n<div class=\"spoiler__content\">\n<p>\u042f \u0431\u0443\u0434\u0443 \u0430\u043a\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f &#171;\u0430\u0431\u0431\u0440\u0435\u0432\u0438\u0430\u0442\u0443\u0440\u0430\u043c\u0438&#187; \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435: \u0432\u0441\u044f\u043a\u043e\u0435 \u043d\u0443\u0434\u043d\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u044f \u0431\u0443\u0434\u0443 \u043f\u0440\u044f\u0442\u0430\u0442\u044c \u0432 \u043d\u0438\u0445. \u0415\u0441\u043b\u0438 \u0432\u044b \u0432\u0438\u0434\u0438\u0442\u0435 \u043f\u043e\u0434\u0447\u0435\u0440\u043a\u043d\u0443\u0442\u043e\u0435 \u0441\u043b\u043e\u0432\u043e &#171;<abbr class=\"habraabbr\" title=\"\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e \u0436\u0435!\" data-title=\"&lt;p>le=&#187;&lt;p>\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e \u0436\u0435!&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr>&#171;, \u043d\u0430\u0432\u0435\u0434\u0438\u0442\u0435 \u0442\u0443\u0434\u0430 \u043c\u044b\u0448\u043a\u0443 \u0438 \u0431\u043e\u043b\u0435\u0435 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u0441\u043f\u043b\u044b\u0442\u044c \u0432 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043a\u0435.<\/p>\n<\/div>\n<\/details>\n<h2>\u0421\u0432\u043e\u0434\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0441\u0443\u043c\u043c\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430<\/h2>\n<p>\u0418\u0442\u0430\u043a, \u0434\u043b\u044f \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0438 \u0431\u0443\u043a\u0432 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u0432\u0435\u0434\u0435\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f: <code>a<\/code>, <code>b<\/code> &#8212; \u0446\u0435\u043d\u044b \u0442\u043e\u0432\u0430\u0440\u043e\u0432, <code>c<\/code> &#8212; \u0441\u0443\u043c\u043c\u0430 \u043d\u0430 \u0440\u0443\u043a\u0430\u0445. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e <code>GCD(a,b)=1<\/code>, \u0438\u043d\u0430\u0447\u0435 <abbr class=\"habraabbr\" title=\"\u041d\u0443 \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0432\u0441\u0435 \u0446\u0435\u043d\u044b \u0443\u043a\u0430\u0437\u0430\u043d\u044b \u043d\u0435 \u0432 \u0435\u0434\u0438\u043d\u0438\u0446\u0430\u0445 \u0434\u0435\u043d\u0435\u0433, \u0430 \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043c\u043e\u043d\u0435\u0442 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u043e\u043c. \u0411\u044e\u0434\u0436\u0435\u0442 \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u044d\u0442\u0438\u0445 \u043c\u043e\u043d\u0435\u0442\u0430\u0445, \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043a\u043e\u043f\u0435\u0439\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0432 \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u0442\u043e\u0440\u0435\u043d\u0438\u044f, \u0432\u0441\u0435-\u0440\u0430\u0432\u043d\u043e \u043d\u0430 \u043d\u0438\u0445 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043a\u0443\u043f\u0438\u0448\u044c.\" data-title=\"&lt;p>\u044d\u0442\u0438\u0445 \u043c\u043e\u043d\u0435\u0442\u0430\u0445, \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043a\u043e\u043f\u0435\u0439\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0432 \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u0442\u043e\u0440\u0435\u043d\u0438\u044f, \u0432\u0441\u0435-\u0440\u0430\u0432\u043d\u043e \u043d\u0430 \u043d\u0438\u0445 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043a\u0443\u043f\u0438\u0448\u044c.&#187; data-title=&lt;p> \u041d\u0443 \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0432\u0441\u0435 \u0446\u0435\u043d\u044b \u0443\u043a\u0430\u0437\u0430\u043d\u044b \u043d\u0435 \u0432 \u0435\u0434\u0438\u043d\u0438\u0446\u0430\u0445 \u0434\u0435\u043d\u0435\u0433, \u0430 \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043c\u043e\u043d\u0435\u0442 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u043e\u043c. \u0411\u044e\u0434\u0436\u0435\u0442 \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u044d\u0442\u0438\u0445 \u043c\u043e\u043d\u0435\u0442\u0430\u0445, \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043a\u043e\u043f\u0435\u0439\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0432 \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u0442\u043e\u0440\u0435\u043d\u0438\u044f, \u0432\u0441\u0435-\u0440\u0430\u0432\u043d\u043e \u043d\u0430 \u043d\u0438\u0445 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043a\u0443\u043f\u0438\u0448\u044c. &lt;\/p>&#187; data-abbr=&#187;\u043c\u043e\u0436\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr> \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u0441\u0435 \u0442\u0440\u0438 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c (\u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 <code>c<\/code>, \u0442\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430\u0446\u0435\u043b\u043e). \u041f\u0443\u0441\u0442\u044c <code>x<\/code> \u0438 <code>y<\/code> &#8212; \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0438 \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u043c\u044b \u043f\u043e\u043a\u0443\u043f\u0430\u0435\u043c. \u0422\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0414\u0438\u043e\u0444\u0430\u043d\u0442\u043e\u0432\u043e \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e:<\/p>\n<p>\u041d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0430 \u0441 \u0434\u0432\u0443\u043c\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u043c\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0432\u043e\u043e\u0431\u0449\u0435 \u0441\u043b\u043e\u0436\u043d\u043e. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043a\u0430\u043a-\u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0434\u043d\u0443 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e. \u042d\u0442\u0430\u043b\u043e\u043d\u043d\u043e\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <code>x<\/code> \u0438 \u0434\u0430\u043b\u044c\u0448\u0435 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <code>y<\/code>. \u041d\u043e \u043a\u0430\u043a \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0443\u0441\u043a\u043e\u0440\u044f\u0442\u044c \u044f \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u043c\u0435\u0441\u0442\u043e \u044d\u0442\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u043f\u043e\u0442\u0440\u0430\u0447\u0435\u043d\u043d\u0443\u044e \u0441\u0443\u043c\u043c\u0443:<\/p>\n<p>\u042d\u0442\u043e \u0443\u0436\u0435 \u0414\u0438\u0430\u0444\u0430\u043d\u0442\u043e\u0432\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u043a\u0430\u043a\u0438\u043c\u0438-\u0442\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c\u0438. \u041d\u043e \u043e\u043d\u043e \u0432\u0435\u0441\u044c\u043c\u0430 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0435 \u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043c\u044b \u0443\u0436\u0435 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u043b\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043e\u0431\u0449\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0439:<\/p>\n<p>\u0438 \u0442\u0443\u0442 &#8212; \u044d\u0442\u043e \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0447\u0435\u0440\u0435\u0437 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A0%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u044d\u0432\u043a\u043b\u0438\u0434\u0430<\/a>. &#8212; \u044d\u0442\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0430\u044f \u043f\u0440\u044b\u0433\u0430\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0439. \u0421\u0434\u0432\u0438\u0433\u0438 \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 <abbr class=\"habraabbr\" title=\"\u0412\u043e\u043e\u0431\u0449\u0435, \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0439 (\u0434\u0430\u0436\u0435 \u043d\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435) \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u0434\u0440\u0443\u0433 \u0438\u0437 \u0434\u0440\u0443\u0433\u0430 \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440. \u041d\u043e \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 GCD(a,b)=1, \u0442\u043e \u044d\u0442\u043e \u0441\u0430\u043c\u044b\u0439 \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u043a\u043e\u043b\u043b\u0438\u043d\u0435\u0430\u0440\u043d\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0439.\" data-title=\"&lt;p>)=1, \u0442\u043e \u044d\u0442\u043e \u0441\u0430\u043c\u044b\u0439 \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u043a\u043e\u043b\u043b\u0438\u043d\u0435\u0430\u0440\u043d\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0439.&#187; data-title=&#187;&lt;p>\u0412\u043e\u043e\u0431\u0449\u0435, \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0439 (\u0434\u0430\u0436\u0435 \u043d\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435) \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u0434\u0440\u0443\u0433 \u0438\u0437 \u0434\u0440\u0443\u0433\u0430 \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440. \u041d\u043e \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 GCD(a,b)=1, \u0442\u043e \u044d\u0442\u043e \u0441\u0430\u043c\u044b\u0439 \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u043a\u043e\u043b\u043b\u0438\u043d\u0435\u0430\u0440\u043d\u044b\u0439 \u043f\u0440\u044f\u043c\u043e\u0439.&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b<\/abbr>. <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c  \u0438 . \u041e\u043d\u0438 \u0434\u0430\u044e\u0442 \u043d\u0430\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043d\u0430 :<\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0446\u0435\u043b\u043e\u0435, \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f:<\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0435 \u0434\u0443\u043c\u0430\u0442\u044c \u043e\u0431 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430\u0445, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0434\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c\u0441\u044f, \u0447\u0442\u043e , . \u042d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e <abbr class=\"habraabbr\" title=\"\u0415\u0441\u043b\u0438 x0 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440 {-b, a} \u043a\u0443\u0447\u0443 \u0440\u0430\u0437. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e y0 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0436\u0435 \u0432\u0435\u043a\u0442\u043e\u0440 \u0435\u0449\u0435 \u043a\u0443\u0447\u0443 \u0440\u0430\u0437.\" data-title=\"&lt;p>\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0436\u0435 \u0432\u0435\u043a\u0442\u043e\u0440 \u0435\u0449\u0435 \u043a\u0443\u0447\u0443 \u0440\u0430\u0437.&#187; data-title=&lt;p>\u0415\u0441\u043b\u0438 x0 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440 {-b, a} \u043a\u0443\u0447\u0443 \u0440\u0430\u0437. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e y0 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0436\u0435 \u0432\u0435\u043a\u0442\u043e\u0440 \u0435\u0449\u0435 \u043a\u0443\u0447\u0443 \u0440\u0430\u0437.&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr> \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f. \u0422\u0443\u0442 \u0436\u0435 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e <abbr class=\"habraabbr\" title=\"\u041f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0438\u0432 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0432 \u044d\u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 (\u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e x0 \u0438 y0) \u043f\u043e\u043b\u0443\u0447\u0438\u043c 0 \u043c\u0435\u043d\u044c\u0448\u0435 i\" data-title=\"&lt;p> x0 \u0438 y0) \u043f\u043e\u043b\u0443\u0447\u0438\u043c 0 \u043c\u0435\u043d\u044c\u0448\u0435 i&#187; data-title=&#187;&lt;p>\u041f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0438\u0432 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0432 \u044d\u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 (\u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e x0 \u0438 y0) \u043f\u043e\u043b\u0443\u0447\u0438\u043c 0 \u043c\u0435\u043d\u044c\u0448\u0435 i&lt;\/p>&lt;p>&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e &#171;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e <\/abbr>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443, \u043e\u043a\u0440\u0443\u0433\u043b\u044f\u044f \u044d\u0442\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432\u0432\u0435\u0440\u0445 \u0438 \u0432\u043d\u0438\u0437 \u043c\u044b \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043d\u0438\u0436\u043d\u044e\u044e \u0433\u0440\u0430\u043d\u0438\u0446\u0443 \u043d\u0430 1 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0435\u0440\u0445\u043d\u0435\u0439 \u0433\u0440\u0430\u043d\u0438\u0446\u044b (\u0435\u0441\u043b\u0438 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u043e\u043a\u0430\u0437\u0430\u043b\u0438\u0441\u044c \u043c\u0435\u0436\u0434\u0443 \u043e\u0434\u043d\u0438\u043c\u0438 \u0438 \u0442\u0435\u043c\u0438 \u0436\u0435 \u0446\u0435\u043b\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438). \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0435\u043b\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 t, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0435 \u0432\u0441\u0435\u043c \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0430\u043c (\u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u0438\u0445 \u0442\u0430\u043c \u0442\u0430\u043a\u0438\u0445 \u043d\u0435\u0442), \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0430\u043a: <\/p>\n<p>\u0410 \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443  \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e <code>c<\/code>, \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0434\u043b\u044f \u043e\u0442\u0432\u0435\u0442\u0430 \u0431\u0443\u0434\u0435\u0442:<\/p>\n<p>\u0422\u0443\u0442 \u0432 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u043a\u0443 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f \u0432\u043d\u0438\u0437 \u0438 \u0432\u0432\u0435\u0440\u0445. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u044b\u0440\u0430\u0437\u0438\u043c ceil \u0447\u0435\u0440\u0435\u0437 floor. \u041e\u043d\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043d\u0430 1, \u043a\u0440\u043e\u043c\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u043a\u043e\u0433\u0434\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e\u0434 ceil \u0446\u0435\u043b\u043e\u0435. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443  \u0438  <abbr class=\"habraabbr\" title=\"\u0415\u0441\u043b\u0438 \u0431\u044b \u0443 \u043d\u0438\u0445 \u0431\u044b\u043b \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u0432\u0430\u0440\u0430\u0436\u0435\u043d\u0438\u0435 x0a+y0b \u043d\u0430 \u043d\u0435\u0433\u043e \u0431\u044b \u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c, \u0430 \u043e\u043d\u043e \u0440\u0430\u0432\u043d\u043e 1\" data-title=\"&lt;p>\u044b \u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c, \u0430 \u043e\u043d\u043e \u0440\u0430\u0432\u043d\u043e 1&#8243; data-title=&lt;p>\u0415\u0441\u043b\u0438 \u0431\u044b \u0443 \u043d\u0438\u0445 \u0431\u044b\u043b \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u0432\u0430\u0440\u0430\u0436\u0435\u043d\u0438\u0435 x0a+y0b \u043d\u0430 \u043d\u0435\u0433\u043e \u0431\u044b \u0434\u0435\u043b\u0438\u043b\u043e\u0441\u044c, \u0430 \u043e\u043d\u043e \u0440\u0430\u0432\u043d\u043e 1&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e &#171;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e <\/abbr>\u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u043f\u043e\u0434 ceil \u0446\u0435\u043b\u043e\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f  \u0434\u0435\u043b\u044f\u0449\u0438\u0445\u0441\u044f \u043d\u0430 . \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0442\u0430\u043c \u0432\u0435\u0437\u0434\u0435 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c ceil=floor+1, \u043d\u043e \u0437\u0430\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0440\u043e\u0432\u043d\u043e \u0432 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f\u0445 \u0443 \u043d\u0430\u0441 \u0432\u044b\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043b\u0438\u0448\u043d\u044f\u044f \u0435\u0434\u0438\u043d\u0438\u0446\u0430, \u0438\u0445 \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u043b\u0435 \u0441\u0443\u043c\u043c\u044b \u043d\u0430\u0437\u0430\u0434 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c. +1 \u043e\u0442 ceil \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c\u0441\u044f \u0441 +1 \u0443\u0436\u0435 \u043f\u043e\u0434 \u0437\u043d\u0430\u043a\u043e\u043c \u0441\u0443\u043c\u043c\u044b \u0438 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c:<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0430\u0437\u043e\u0431\u044c\u0435\u043c \u0441\u0443\u043c\u043c\u0443 \u043d\u0430 \u0434\u0432\u0435 \u0438 \u0432\u0432\u0435\u0434\u0435\u043c \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e:<\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435, \u043e\u0442\u0432\u0435\u0442 \u043a \u0437\u0430\u0434\u0430\u0447\u0435:<\/p>\n<h2>\u0412\u044b\u0432\u043e\u0434\u0438\u043c \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u0441\u0443\u043c\u043c\u044b<\/h2>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0441\u0442\u0430\u043b\u0430\u0441\u044c \u0441\u0430\u043c\u0430\u044f \u043c\u0430\u043b\u043e\u0441\u0442\u044c: \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0432 <code>SumFloor<\/code> \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c.<\/p>\n<h3>\u0411\u043e\u0440\u0435\u043c\u0441\u044f \u0441 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u043c\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c\u0438<\/h3>\n<p>\u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e  \u0438 \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b. \u041c\u043e\u0436\u043d\u043e \u0438\u0445 \u043d\u0430 \u041d\u041e\u0414 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c, \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u0432 \u043d\u0438 \u043e\u0434\u043d\u043e \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u0435. \u041d\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u0447\u0438\u0441\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432 \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f, \u0443\u0436\u0435 \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b (\u0441\u043c. &#171;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187; \u0432\u044b\u0448\u0435). \u041d\u043e \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c GCD \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e &#8212; \u043d\u0430 \u043e\u0446\u0435\u043d\u043a\u0443 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u043e \u043d\u0435 \u043f\u043e\u0432\u043b\u0438\u044f\u0435\u0442.<\/p>\n<p>\u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e . \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u043b\u0438\u0448\u043d\u044e\u044e \u0447\u0430\u0441\u0442\u044c, \u0435\u0441\u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c\u0432 \u0441\u0443\u043c\u043c\u0443 \u0438 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0432\u0441\u0435 \u0446\u0435\u043b\u043e\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0432 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u0438:<\/p>\n<p>\u0418\u043b\u0438:<\/p>\n<p>\u0412\u043e\u0442 \u043c\u044b \u0438 \u0432\u044b\u0440\u0430\u0437\u0438\u043b\u0438 \u0441\u0443\u043c\u043c\u0443 \u0441 \u0447\u0435\u0440\u0435\u0437 \u0441\u0443\u043c\u043c\u0443 c .<\/p>\n<p>\u0412\u043e-\u0442\u0440\u0435\u0442\u044c\u0438\u0445, \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e . \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u043d\u0430 \u043a\u0443\u0441\u043a\u0438, \u043f\u0435\u0440\u0432\u044b\u0439 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043f\u043e \u0447\u0438\u0441\u0435\u043b, \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c m. \u041f\u0443\u0441\u0442\u044c , \u0442\u043e\u0433\u0434\u0430:<\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0442\u0440\u0438\u043c \u043b\u0435\u0432\u0443\u044e \u0438 \u043f\u0440\u0430\u0432\u0443\u044e \u0441\u0443\u043c\u043c\u044b. \u0412 \u043b\u0435\u0432\u043e\u0439 \u0441\u0443\u043c\u043c\u0435 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e\u043c \u0438 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u043d\u0435-\u043c\u043e\u0434\u0443\u043b\u0438 \u043a\u0430\u043a \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u044e:<\/p>\n<p>\u0412 \u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0439\u0441\u044f \u0441\u0443\u043c\u043c\u0435  \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e  \u0440\u043e\u0432\u043d\u043e  \u0440\u0430\u0437. \u0410 \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443  \u0438  \u0432\u0437\u0430\u0438\u043c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e <abbr class=\"habraabbr\" title=\"\u0420\u0430\u0437 k \u0438 m \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0443 k \u0435\u0441\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e m. \u0410 \u0437\u043d\u0430\u0447\u0438\u0442 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 ki%m=x \u0438\u043c\u0435\u0435\u0442 \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 x\" data-title=\"&lt;p> \u0438\u043c\u0435\u0435\u0442 \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 x&#187; data-title=&#187;&lt;p>\u0420\u0430\u0437 k \u0438 m \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0443 k \u0435\u0441\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e m. \u0410 \u0437\u043d\u0430\u0447\u0438\u0442 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 ki%m=x \u0438\u043c\u0435\u0435\u0442 \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 x&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e &#171;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e <\/abbr>\u0442\u043e\u0436\u0435 \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e  \u0440\u043e\u0432\u043d\u043e\u0440\u0430\u0437, \u043d\u043e \u0432 \u043a\u0430\u043a\u043e\u043c-\u0442\u043e \u0434\u0440\u0443\u0433\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u041d\u043e \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0430\u043c \u043d\u0435 \u0432\u0430\u0436\u0435\u043d, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0440\u0430\u0437 \u043f\u0440\u043e\u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043e\u0442 0 \u0434\u043e . \u0418\u0442\u0430\u043a, \u043b\u0435\u0432\u0430\u044f \u0441\u0443\u043c\u043c\u0430 \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e:<\/p>\n<p>\u0412 \u043f\u0440\u0430\u0432\u043e\u0439 \u0441\u0443\u043c\u043c\u0435 \u0437\u0430\u043c\u0435\u043d\u0438\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e :<\/p>\n<p>\u0421\u043e\u0431\u0438\u0440\u0430\u044f \u0432\u0441\u0435 \u0432\u043c\u0435\u0441\u0442\u0435, \u043f\u043e\u043c\u043d\u044f, \u0447\u0442\u043e :<\/p>\n<p>\u0412\u043e\u0442 \u043c\u044b \u0438 \u0432\u044b\u0440\u0430\u0437\u0438\u043b\u0438 \u0441\u0443\u043c\u043c\u0443 \u0434\u043e \u0447\u0435\u0440\u0435\u0437 \u0441\u0443\u043c\u043c\u0443 \u0434\u043e .<\/p>\n<h3>\u0412\u044b\u0432\u043e\u0434\u0438\u043c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u043e\u0431\u0449\u0435\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f<\/h3>\n<p>\u0418\u0442\u0430\u043a, \u043c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e , , .<\/p>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u0433\u043b\u0430\u0432\u043d\u0430\u044f \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u044c \u0442\u0443\u0442, \u044d\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Hermite%27s_identity\" rel=\"noopener noreferrer nofollow\">Hermite&#8217;s identity<\/a>. \u042f \u043c\u043d\u043e\u0433\u043e \u0441 \u043d\u0438\u043c \u044d\u043a\u0441\u043f\u0435\u0440\u0435\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0438 \u0441\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u0437\u0430\u0447\u0438\u0441\u043b\u043e , \u0430 \u0437\u0430 \u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0435\u0441\u044f :<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u043e \u044d\u0442\u043e \u0431\u044b\u0432\u0430\u0435\u0442 \u0441\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u043c\u0438 \u0441\u0443\u043c\u043c\u0430\u043c\u0438, \u0438\u043d\u0442\u0435\u0433\u0440\u0430\u043b\u0430\u043c\u0438 \u0438\u043b\u0438 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u043c\u0438, \u043d\u0430\u0434\u043e \u043f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0438\u0445 \u043f\u043e\u0440\u044f\u0434\u043e\u043a:<\/p>\n<p>\u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0434\u043e\u0433\u0430\u0434\u043a\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u043e\u0434 \u0437\u043d\u0430\u043a\u043e\u043c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f \u0432\u043d\u0438\u0437 \u0441\u0442\u043e\u0438\u0442 \u0441\u0443\u043c\u043c\u0430 \u0438\u0437 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b, \u043c\u0435\u043d\u044c\u0448\u0438\u0445 1 \u043a\u0430\u0436\u0434\u043e\u0435! \u0412\u0435\u0434\u044c \u0438 . \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 floor \u0431\u0443\u0434\u0435\u0442 \u0438\u043b\u0438 0 \u0438\u043b\u0438 1. 1 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 . \u041e\u0442\u0441\u044e\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 , \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0447\u0442\u043e-\u0442\u043e \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0432\u043e\u043e\u0431\u0449\u0435 \u0441\u0443\u043c\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f: . \u0422.\u043a. \u0446\u0435\u043b\u043e\u0435, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043f\u0438\u0441\u0430\u0442\u044c:<\/p>\n<p>\u041d\u043e \u0441\u0443\u043c\u043c\u0430 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u043f\u043e \u0431\u044b\u043b\u0430 \u043e\u0442 0 \u0434\u043e \u043f\u043e\u044d\u0442\u043e\u043c\u0443, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0434\u0438\u043d\u0438\u0446\u044b, \u043d\u0430\u0434\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438\u0445 \u043e\u0442 \u0434\u043e . \u041a\u043e\u0433\u0434\u0430 \u044d\u0442\u0430 \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 \u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u0445 \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445 \u0431\u0443\u0434\u0435\u0442 . \u0415\u0441\u043b\u0438 \u0436\u0435 \u044d\u0442\u0430 \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u0442\u043e \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0441\u0443\u043c\u043c\u0435 \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442, \u043d\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0432\u044b\u0448\u0435 \u0434\u0430\u0441\u0442 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044d\u0442\u0443 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c, \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0433\u0434\u0430 \u043e\u043d\u0430 \u0434\u0430\u0435\u0442 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0430 , \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u044d\u0442\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f:<\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0441\u0433\u0440\u0443\u043f\u0438\u0440\u043e\u0432\u0430\u0442\u044c floor \u0438 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u043f\u043e \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0442\u043e\u0440\u043e\u043d\u044b. \u0414\u0430\u043b\u044c\u0448\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u043e \u0432\u0438\u0434\u0430 \u0415\u0433\u043e \u043c\u043e\u0436\u043d\u043e <abbr class=\"habraabbr\" title=\"\u0412\u0435\u0434\u044c \u0435\u0441\u043b\u0438 x \u043c\u0435\u043d\u044c\u0448\u0435 N, \u0442\u043e \u0438 floor(x) \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435. \u0410 \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 floor  \u0446\u0435\u043b\u043e\u0435 N \u043d\u0435 \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a.\" data-title=\"&lt;p>\u043b\u043e\u0435 N \u043d\u0435 \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a.&#187; data-title=&#187;&lt;p>\u0412\u0435\u0434\u044c \u0435\u0441\u043b\u0438 x \u043c\u0435\u043d\u044c\u0448\u0435 N, \u0442\u043e \u0438 floor(x) \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435. \u0410 \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 floor  \u0446\u0435\u043b\u043e\u0435 N \u043d\u0435 \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a.&lt;\/p>&lt;p>&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr> \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 <\/p>\n<p>\u0422.\u043a. \u0446\u0435\u043b\u043e\u0435:<\/p>\n<p>\u042d\u0442\u043e \u0447\u0438\u0441\u043b\u043e, \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u0432\u044b\u043a\u043b\u0430\u0434\u043e\u043a \u043d\u0438\u0436\u0435, \u043d\u0430\u0437\u043e\u0432\u0435\u043c .<\/p>\n<p>\u0418\u0442\u0430\u043a, \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0442 \u0434\u043e , \u0430 \u0432\u043d\u0443\u0442\u0440\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0441\u0443\u043c\u043c\u0430 \u0441\u043a\u043e\u043b\u044c\u043a\u0438-\u0442\u043e \u0435\u0434\u0438\u043d\u0438\u0446. \u0418\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u044b \u0443\u0436\u0435 \u0441\u0447\u0438\u0442\u0430\u043b\u0438 \u0432\u044b\u0448\u0435. \u0418\u0442\u043e\u0433\u043e\u0432\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430:<\/p>\n<p>\u041f\u043e\u043b\u0435\u0437\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e (<abbr class=\"habraabbr\" title=\"\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0435, \u0442.\u043a. \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432\u0432\u0435\u0440\u0445 \u0441\u0442\u043e\u0438\u0442 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0437\u043d\u0430\u043a\u0430 \u043c\u0435\u043d\u044c\u0448\u0435. \u041f\u043e\u0442\u043e\u043c \u0432\u0441\u0435 \u0443\u043f\u0440\u043e\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430.\" data-title=\"&lt;p>\u0430\u043a\u0430 \u043c\u0435\u043d\u044c\u0448\u0435. \u041f\u043e\u0442\u043e\u043c \u0432\u0441\u0435 \u0443\u043f\u0440\u043e\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430.&#187; data-title=&#187;&lt;p>\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u0440\u0430\u0432\u043d\u0435\u0441\u0442\u0432\u0435, \u0442.\u043a. \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0432\u0432\u0435\u0440\u0445 \u0441\u0442\u043e\u0438\u0442 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0437\u043d\u0430\u043a\u0430 \u043c\u0435\u043d\u044c\u0448\u0435. \u041f\u043e\u0442\u043e\u043c \u0432\u0441\u0435 \u0443\u043f\u0440\u043e\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430.&lt;\/p>&lt;p>&lt;\/p>&#187; data-abbr=&#187;\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e&#187;>\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e<\/abbr>), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u0430\u043f\u0438\u0441\u044c \u0432\u044b\u0448\u0435 \u0438\u043c\u0435\u0435\u0442 \u0441\u043c\u044b\u0441\u043b. \u041d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043f\u043e\u0440\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441, \u0430 \u0447\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442, \u0435\u0441\u043b\u0438 , \u043d\u043e \u044d\u0442\u043e\u0442 \u0441\u043b\u0443\u0447\u0430\u0439 \u043d\u0430\u043c \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0434\u0430\u043b\u044c\u0448\u0435 \u0438 \u0432 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c, \u0447\u0442\u043e \u0441\u0443\u043c\u043c\u0430 0 \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445 \u0440\u0430\u0432\u043d\u0430 0.<\/p>\n<p>\u0426\u0435\u043b\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u043d\u0435\u0441\u0442\u0438 \u0437\u0430 \u0437\u043d\u0430\u043a \u0441\u0443\u043c\u043c\u044b, \u043f\u043e\u043b\u0443\u0447\u0438\u0432 (\u0438 \u0434\u0430\u0436\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435  \u0432\u0441\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442). \u041e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0447\u0442\u0438 SumFloor(*, m, k), \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043e\u0442 \u0442\u0430\u043c \u0441\u0443\u043c\u043c\u0430 \u043d\u0435 \u043e\u0442 0 \u0434\u043e \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0447\u0438\u0441\u043b\u0430, \u0430 \u043e\u0442 N&#8217; \u0434\u043e \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u042d\u0442\u0443 \u0441\u0443\u043c\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c, \u043a\u0430\u043a . <\/p>\n<p>\u041f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0439 \u0438\u0442\u043e\u0433:<\/p>\n<p>\u0414\u0430\u043b\u0435\u0435, \u0432\u0441\u043f\u043e\u043c\u0438\u043d\u0430\u044f, \u043a\u0430\u043a \u043c\u044b \u0431\u043e\u0440\u043e\u043b\u0438\u0441\u044c \u0441 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u043c\u0438 \u0441\u043b\u0443\u0447\u0430\u044f\u043c\u0438, \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0443\u043c\u043c\u0430 \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043e:<\/p>\n<\/p>\n<p>\u0410 \u0432\u0442\u043e\u0440\u0430\u044f \u0434\u043e:<\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c (\u043d\u0430\u043f\u043e\u043c\u043d\u0438\u0430\u044e, \u0447\u0442\u043e )<\/p>\n<p>\u041f\u0440\u0438 \u044d\u0442\u043e\u043c, \u0432\u044b\u0448\u0435 \u043c\u044b \u0443\u0436\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0438, \u0447\u0442\u043e . \u0422\u0430\u043a\u0436\u0435, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e . \u0422\u0430\u043a\u0436\u0435, \u0438 \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u043f\u0440\u043e\u0441\u0442\u044b. \u041f\u043e\u044d\u0442\u043e\u043c\u0443, \u043f\u043e\u0441\u043b\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043c\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u0441\u0442\u0430\u043d\u0435\u043c\u0441\u044f \u0432 \u0442\u043e\u043c \u0436\u0435 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043f\u044f\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043d\u0435 \u043d\u0430\u0434\u043e.<\/p>\n<p>\u0410 \u0431\u0430\u0437\u0430 \u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438, \u0435\u0441\u043b\u0438 , \u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 0. \u0415\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u0438 \u0432\u044b\u0434\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438 . \u0418\u043b\u0438, \u0435\u0441\u043b\u0438 , \u0442\u043e \u0441\u0443\u043c\u043c\u0430 \u043d\u0438\u0447\u0435\u0433\u043e &#8212; \u043d\u043e\u043b\u044c.<\/p>\n<p>\u041f\u043e\u0434\u043e\u0431\u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u042d\u0432\u043a\u043b\u0438\u0434\u0430 \u0434\u043b\u044f GCD, \u044d\u0442\u0430 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0437\u0430 . \u0415\u0433\u043e \u0435\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0438 \u043a\u043e\u0434:<\/p>\n<pre><code class=\"cpp\">\/\/ \u0420\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u042d\u0432\u043a\u043b\u0438\u0434\u0430 \/\/ \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 GCD(a,b) \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 x, y, \u0442.\u0447. a*x+b*y=GCD(a,b) int GcdEx(int a, int b, int &amp;x, int &amp;y) {     if (b == 0) {         x = 1;         y = 0;         return a;     }     if (b > a) return GcdEx(b, a, y, x);     int xx, yy;     int d = GcdEx(b, a % b, xx, yy);     y = xx - a\/b*yy;     x = yy;     return d; }  \/\/<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-349994","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/349994","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=349994"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/349994\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=349994"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=349994"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=349994"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}