{"id":362412,"date":"2024-05-21T01:34:35","date_gmt":"2024-05-21T01:34:35","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=362412"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=362412","title":{"rendered":"<span>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/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><em>\u0410\u0432\u0442\u043e\u0440 \u0441\u0442\u0430\u0442\u044c\u0438 \u2014 \u0412\u0438\u043a\u0442\u043e\u0440\u0438\u044f \u041b\u044f\u043b\u0438\u043a\u043e\u0432\u0430<\/em><\/p>\n<p>\u0412 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043c\u044b \u0443\u0436\u0435 \u0442\u0430\u043a \u043f\u0440\u0438\u0432\u044b\u043a\u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0433\u043e\u0442\u043e\u0432\u044b\u043c\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c\u0438, \u0447\u0442\u043e \u043f\u0440\u0438 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0438 \u0432\u044b\u0441\u043e\u043a\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e\u0433\u043e \u043a\u043e\u0434\u0430, \u0434\u0430\u0436\u0435 \u043d\u0435 \u0437\u0430\u0434\u0443\u043c\u044b\u0432\u0430\u0435\u043c\u0441\u044f \u043d\u0430\u0434 \u0442\u0435\u043c, \u0430 \u043a\u0430\u043a \u0432\u043e\u043e\u0431\u0449\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b \u0442\u0435 \u0438\u043b\u0438 \u0438\u043d\u044b\u0435 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u044b. \u0418 \u0443\u0436 \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0447\u0438\u0441\u0435\u043b \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u043c\u044b \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u0437\u0430\u0434\u0443\u043c\u044b\u0432\u0430\u0435\u043c\u0441\u044f \u043e \u0442\u043e\u043c, \u0430 \u043a\u0430\u043a \u0432\u043e\u043e\u0431\u0449\u0435 \u0432\u0441\u0435 \u044d\u0442\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e. \u0418 \u043a\u0430\u043a\u0438\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e?<\/p>\n<p>\u0412\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0435. \u0427\u0442\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u0442\u0430\u043a\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c? \u041a\u0430\u043a \u043d\u0430\u043c \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e \u0435\u0449\u0435 \u0441\u043e \u0448\u043a\u043e\u043b\u044b \u2014 \u044d\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u0441\u0435\u0431\u044f. \u041d\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043a\u0440\u043e\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438.<\/p>\n<p>\u041c\u043d\u043e\u0433\u0438\u0435 \u0438\u0437 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c n \u0447\u0438\u0441\u043b\u0430 x \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0442\u044c x \u043d\u0430 \u0441\u0430\u043c\u043e \u0441\u0435\u0431\u044f n \u0440\u0430\u0437, \u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u0443\u0436\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438. \u0422\u0430\u043a\u0436\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0446\u0438\u0444\u0440\u044b \u0432 \u0441\u043e\u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u044e\u0442\u0441\u044f. \u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b.\u00a0<\/p>\n<p>\u0417\u0430\u0447\u0435\u043c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c?<strong> <\/strong>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043e\u043f\u0435\u0440\u0438\u0440\u0443\u044e\u0442 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0434\u043b\u0438\u043d\u043e\u0439 \u0432 \u0442\u044b\u0441\u044f\u0447\u0438 \u0431\u0438\u0442. \u0412 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u0438 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043c\u043e\u0434\u0435\u043b\u0435\u0439: \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445, \u043d\u0435\u0439\u0440\u043e\u0441\u0435\u0442\u0435\u0432\u044b\u0445, \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u0438 \u0434\u0440. \u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0434\u043b\u044f \u0437\u0430\u0449\u0438\u0442\u044b \u043f\u0430\u0440\u043e\u043b\u0435\u0439 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u043a\u043e\u043d\u0444\u0438\u0434\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0442\u043e\u0436\u0435 \u043d\u0435 \u043e\u0431\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0431\u0435\u0437 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0418 \u044d\u0442\u043e\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0442\u044c \u0434\u0430\u043b\u044c\u0448\u0435. \u041c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432.<\/p>\n<h3>\u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/h3>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0447\u0435\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 x \u0438 n \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043c\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0435 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x^n=(x^{n\/2})^2=x^{n\/2}\\cdot{x^{n\/2}}\" alt=\"x^n=(x^{n\/2})^2=x^{n\/2}\\cdot{x^{n\/2}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/73d\/41f\/0d9\/73d41f0d981dfda2e388fca481261be8.svg\" width=\"218\" height=\"26\"\/><\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0437\u0430 \u043e\u0434\u043d\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0441\u0432\u0435\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0432\u0434\u0432\u043e\u0435 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438.<\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0447\u0435\u0442\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0435<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x^{2^m}=(((x^2)^2)^2....)^2.\" alt=\"x^{2^m}=(((x^2)^2)^2....)^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fe2\/e42\/e9c\/fe2e42e9cb64878630af00a2d8f4fb58.svg\" width=\"189\" height=\"25\"\/><\/p>\n<p>\u0415\u0441\u043b\u0438 n \u043d\u0435\u0447\u0435\u0442\u043d\u0430, \u0442\u043e\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0441\u0442\u0435\u043f\u0435\u043d\u0438 (n-1),\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0443\u0436\u0435 \u0431\u0443\u0434\u0435\u0442 \u0447\u0435\u0442\u043d\u043e\u0439.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x^n=x^{n-1}\\cdot{x}\" alt=\"x^n=x^{n-1}\\cdot{x}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/87e\/184\/d74\/87e184d749c0b3510222666457ca6f7c.svg\" width=\"112\" height=\"21\"\/><\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0440\u0435\u043a\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430: \u043e\u0442 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u043c\u044b \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 \u0447\u0435\u0442\u043d\u0430<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\u043a n\/2\" alt=\"\u043a n\/2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c12\/74a\/a49\/c1274aa49742f3fa420c52114378dc31.svg\" width=\"39\" height=\"27\"\/><\/p>\n<p>\u0430 \u0438\u043d\u0430\u0447\u0435 \u2014 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\u043a n-1\" alt=\"\u043a n-1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f0b\/56f\/412\/f0b56f41260ac259bfe95d4ae3e2187f.svg\" width=\"54\" height=\"27\"\/><\/p>\n<p>\u0418 \u0442\u043e\u0433\u0434\u0430 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c m \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u0442\u043e\u0447\u043d\u0435\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.<\/p>\n<p>\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u043c \u044d\u0442\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0435 \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u0435 \u043d\u0430 \u043e\u0431\u0449\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439, \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432\u0448\u0438\u0441\u044c \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e\u043c<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{blue}{x}^\\color{green}n=\\begin{cases}\\color{blue}{x}(\\color{blue}{x}^2)^{(\\color{green}{n}-1)\/2} &amp;\\text {\u0435\u0441\u043b\u0438 $\\color{green}{n}$ \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435} \\\\ (\\color{blue}x^2)^{\\color{green}{n}\/2}, &amp;\\text{\u0435\u0441\u043b\u0438 $\\color{green}{n}$ \u0447\u0435\u0442\u043d\u043e\u0435} \\\\ 1, &amp;\\text {\u0435\u0441\u043b\u0438 $\\color{green}{n}=0$} \\end {cases}\" alt=\"\\color{blue}{x}^\\color{green}n=\\begin{cases}\\color{blue}{x}(\\color{blue}{x}^2)^{(\\color{green}{n}-1)\/2} &amp;\\text {\u0435\u0441\u043b\u0438 $\\color{green}{n}$ \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435} \\\\ (\\color{blue}x^2)^{\\color{green}{n}\/2}, &amp;\\text{\u0435\u0441\u043b\u0438 $\\color{green}{n}$ \u0447\u0435\u0442\u043d\u043e\u0435} \\\\ 1, &amp;\\text {\u0435\u0441\u043b\u0438 $\\color{green}{n}=0$} \\end {cases}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ce8\/6bf\/2f4\/ce86bf2f43351081f6d0d41fb4f077dc.svg\" width=\"305\" height=\"84\"\/><\/p>\n<p>\u0415\u0441\u043b\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n&lt;0, \u0442\u043e\u0433\u0434\u0430<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{blue}{x}^{\\color{green}{-n}}=\\Big(\\frac{1}{\\color{blue}{x}}\\Big)^\\color{green}{n}=\\frac{1}{\\color{blue}{x}^\\color{green}{n}}\" alt=\"\\color{blue}{x}^{\\color{green}{-n}}=\\Big(\\frac{1}{\\color{blue}{x}}\\Big)^\\color{green}{n}=\\frac{1}{\\color{blue}{x}^\\color{green}{n}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7c6\/b8c\/c7c\/7c6b8cc7c3bc50f84dd0e92556a98ab8.svg\" width=\"159\" height=\"43\"\/><\/p>\n<p>\u0412\u0441\u0435\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 2logn \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432, \u043f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043c\u044b \u043f\u0440\u0438\u0434\u0435\u043c \u043a n=0. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u0437\u0430 O(log n) \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439.<\/p>\n<p>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u043e\u0439, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mu_n=\\xi_n+2\\varepsilon_n-2\" alt=\"\\mu_n=\\xi_n+2\\varepsilon_n-2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d3a\/e62\/fec\/d3ae62fecad2d6cacfd86f489ff9206e.svg\" width=\"154\" height=\"21\"\/><\/p>\n<p>\u0433\u0434\u0435<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\xi_n\" alt=\"\\xi_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6a4\/c64\/011\/6a4c64011e8bdef6114c7dfe3722edd4.svg\" width=\"19\" height=\"21\"\/><\/p>\n<p>\u0438 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\varepsilon_n\" alt=\"\\varepsilon_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/464\/91a\/6af\/46491a6af8f96a12f234e621ce1af361.svg\" width=\"19\" height=\"15\"\/><\/p>\n<p>\u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043d\u0443\u043b\u0435\u0439 \u0438 \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u0447\u0438\u0441\u043b\u0430 n. \u042d\u0442\u0430 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0430 \u0440\u0430\u0441\u0442\u0435\u0442 \u043a\u0440\u0430\u0439\u043d\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0441 \u0440\u043e\u0441\u0442\u043e\u043c n.<\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u043d\u0430\u043c \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432 10000000000-\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u0442\u043e \u043c\u044b \u043e\u0431\u043e\u0448\u043b\u0438\u0441\u044c \u0431\u044b \u0432\u0441\u0435\u0433\u043e 43 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f\u043c\u0438. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0438\u0442\u043c<\/p>\n<pre><code>def my_power(val,p):     if p&lt;0:         return my_power(1\/val, -p)     if p==0:         return 1     if p%2 == 0:         return my_power(val*val, p\/2)     else:         return val*power(val*val,(p-1)\/2)<\/code><\/pre>\n<p>\u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u043c \u0432\u044b\u0437\u043e\u0432\u0435 \u0432 \u044d\u0442\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f \u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0446\u0438\u0444\u0440\u044b \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n. \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0431\u0438\u0442\u043e\u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f n. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432 \u0440\u0430\u0432\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 1 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 n.<\/p>\n<p>\u041d\u043e \u0435\u0441\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u043e\u0435 \u0441 \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u043c \u043e\u0431\u044a\u0435\u043c\u043e\u043c \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u0435\u043d \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u2014 \u0438\u043b\u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u0435\u0441\u043b\u0438 \u043e\u0431\u044a\u0435\u043c \u043d\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f.<\/p>\n<h3>\u0411\u0438\u043d\u0430\u0440\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/h3>\n<p>\u041e\u0434\u0438\u043d \u0438\u0437 \u0441\u0430\u043c\u044b\u0445 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0414\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438. \u0417\u0430 \u0441\u0447\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438, \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f, \u0432\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435 \u0447\u0435\u0433\u043e \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f. \u0422\u0430\u043a\u0436\u0435 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043f\u0440\u0438 \u043b\u044e\u0431\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>\u0421\u0443\u0442\u044c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u0432 \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 \u0447\u0438\u0441\u043b\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u0432\u0438\u0434\u0435. \u0418 \u0434\u0430\u043b\u0435\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u0431\u0438\u0442\u0430\u043c \u044d\u0442\u043e\u0433\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430. \u0422\u0430\u043a\u043e\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0431\u0438\u0442\u044b \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b.\u00a0<\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0435 \u0441\u0445\u0435\u043c\u0443 \u201c\u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e\u201d \u0438 \u0441\u0445\u0435\u043c\u0443 \u201c\u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e\u201d. \u0414\u043b\u044f \u0432\u0441\u0435\u0445 \u044d\u0442\u0438\u0445 \u0441\u0445\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e \u0438 \u0440\u0430\u0432\u043d\u043e k, \u0433\u0434\u0435 k \u2014 \u0434\u043b\u0438\u043d\u0430 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 n \u0431\u0438\u0442\u0430\u0445, <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"k\\sim{ln(n)}\" alt=\"k\\sim{ln(n)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/59d\/16f\/61e\/59d16f61e38ae48281c4b035666f42a7.svg\" width=\"81\" height=\"22\"\/><\/p>\n<p>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0436\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u0447\u0438\u0441\u043b\u0430 n. \u0412 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\frac{1}{2}\\cdot{ln(n)}\" alt=\"\\frac{1}{2}\\cdot{ln(n)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a27\/7cb\/d2a\/a277cbd2aceb5bdfce56464dbf0a1624.svg\" width=\"76\" height=\"43\"\/><\/p>\n<p>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0432 \u0441\u043e\u0442\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u044d\u0442\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c 8 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442. \u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043f\u0440\u0438 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f n-1 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f, \u0442\u043e \u0435\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0446\u0435\u043d\u0435\u043d\u043e \u043a\u0430\u043a O(n).<\/p>\n<h2>\u0421\u0445\u0435\u043c\u0430 \u00ab\u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e\u00bb<\/h2>\n<p>\u041d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u0441\u0430\u043c\u043e \u0437\u0430 \u0441\u0435\u0431\u044f, \u0432 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u0435 \u0431\u0438\u0442\u044b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u0442 \u0441\u0442\u0430\u0440\u0448\u0435\u0433\u043e \u043a \u043c\u043b\u0430\u0434\u0448\u0435\u043c\u0443.<\/p>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u044c n \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"n = (m_km_{k-1}...m_1m_0)_2\" alt=\"n = (m_km_{k-1}...m_1m_0)_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b98\/32d\/5be\/b9832d5be5958c1871804d204c442e52.svg\" width=\"211\" height=\"22\"\/><\/p>\n<p>\u0422\u043e\u0433\u0434\u0430<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"n=\\color{green}{m_k}\\cdot2^\\color{green}{^k}+\\color{blue}{m_{k-1}}\\cdot2^\\color{blue}{{k-1}}+...\\color{purple}{m_1}\\cdot2\\color{purple}{^1}+\\color{red}{m_0}\" alt=\"n=\\color{green}{m_k}\\cdot2^\\color{green}{^k}+\\color{blue}{m_{k-1}}\\cdot2^\\color{blue}{{k-1}}+...\\color{purple}{m_1}\\cdot2\\color{purple}{^1}+\\color{red}{m_0}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/557\/833\/dfb\/557833dfb310e76bd574e66ef8092693.svg\" width=\"366\" height=\"27\"\/><\/p>\n<p>\u0433\u0434\u0435 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"m_i = {0,1}\" alt=\"m_i = {0,1}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c30\/962\/fcc\/c30962fcc805e2f9544573f69eab17c7.svg\" width=\"78\" height=\"20\"\/><\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 \u0447\u0438\u0441\u043b\u043e x \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0442\u0430\u043a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_n=x^{((...((m_k\\cdot2+m_{k-1})\\cdot2+m_{k-2})\\cdot2+....)\\cdot2+m_1)\\cdot2+m_0} x_n={((...(((x^{\\color{green}{m_k}})^2x^{\\color{blue}{m_{k-1}}})^2....)^2x^\\color{purple}{m_1})x^\\color{red}{m_0}}\" alt=\"x_n=x^{((...((m_k\\cdot2+m_{k-1})\\cdot2+m_{k-2})\\cdot2+....)\\cdot2+m_1)\\cdot2+m_0} x_n={((...(((x^{\\color{green}{m_k}})^2x^{\\color{blue}{m_{k-1}}})^2....)^2x^\\color{purple}{m_1})x^\\color{red}{m_0}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/230\/a96\/6cc\/230a966cc167680ab7f1d6f3c35a98c4.svg\" width=\"699\" height=\"26\"\/><\/p>\n<p>\u0418 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c<\/p>\n<ol>\n<li>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043a\u043e\u0434\u0435.<\/p>\n<\/li>\n<li>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 i \u0438 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043e\u0442 k-1 \u0434\u043e 0.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=1, \u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0438 \u0437\u0430\u0442\u0435\u043c \u0443\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u043d\u0430 \u0445.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=0, \u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.\u00a0<\/p>\n<\/li>\n<\/ol>\n<p>\u0418\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\begin{cases}s_1=x \\\\ s_{i+1} = s_i^2{\\cdot}x^{m_k-i} \\\\ i=1,2,...,k \\end {cases}\" alt=\"\\begin{cases}s_1=x \\\\ s_{i+1} = s_i^2{\\cdot}x^{m_k-i} \\\\ i=1,2,...,k \\end {cases}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/84f\/f08\/a25\/84ff08a25542c8076cd791e156311745.svg\" width=\"154\" height=\"72\"\/><\/p>\n<p>\u041f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0432 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"21_{11}, x=21, n=11\" alt=\"21_{11}, x=21, n=11\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/588\/e00\/cc9\/588e00cc91217386f9bfd8603ef50a5d.svg\" width=\"167\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"11_{10}=\\color{green}{1}\\color{blue}{0}\\color{purple}{1}\\color{red}{1}2\" alt=\"11_{10}=\\color{green}{1}\\color{blue}{0}\\color{purple}{1}\\color{red}{1}2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/561\/b46\/55a\/561b4655a2840faa8629058bf433a1ce.svg\" width=\"110\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{green}{m_3} = 1, \\color{blue}{m_2} = 0, \\color{purple}{m_1} = 1, \\color{red}{m_0} =1\" alt=\"\\color{green}{m_3} = 1, \\color{blue}{m_2} = 0, \\color{purple}{m_1} = 1, \\color{red}{m_0} =1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e9b\/b25\/5b6\/e9bb255b6cf8b742259fcd568c9112d2.svg\" width=\"274\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"21{11}=(((1\\cdot21^\\color{green}{m_3})^2\\cdot21^\\color{blue}{m2})^2\\cdot21^\\color{purple}{m_1})^2\\cdot21^\\color{red}{m_0}=\" alt=\"21{11}=(((1\\cdot21^\\color{green}{m_3})^2\\cdot21^\\color{blue}{m2})^2\\cdot21^\\color{purple}{m_1})^2\\cdot21^\\color{red}{m_0}=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/330\/d27\/351\/330d27351c7a43cd69d6bf81bb98ead8.svg\" width=\"385\" height=\"25\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"0=(((1\\cdot21^\\color{green}{1})^2\\cdot21^\\color{blue}{0})^2\\cdot21^\\color{purple}1)^221^\\color{red}{1}=\" alt=\"0=(((1\\cdot21^\\color{green}{1})^2\\cdot21^\\color{blue}{0})^2\\cdot21^\\color{purple}1)^221^\\color{red}{1}=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/adf\/d8f\/440\/adfd8f440ae51f4a3eb9adad2a561168.svg\" width=\"295\" height=\"25\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=(((1\\cdot21)^2\\cdot1)^2\\cdot21)^2\\cdot21=\" alt=\"=(((1\\cdot21)^2\\cdot1)^2\\cdot21)^2\\cdot21=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/afa\/d94\/c6d\/afad94c6dddee5fa6de5a55e6ea1e28e.svg\" width=\"249\" height=\"25\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=(((21)^2)^2\\cdot21)^2\\cdot21=\" alt=\"=(((21)^2)^2\\cdot21)^2\\cdot21=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e59\/369\/bf5\/e59369bf51966743a66cf94a88cc0c6e.svg\" width=\"201\" height=\"25\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=(((441)^2\\cdot21)^2\\cdot21=\" alt=\"=(((441)^2\\cdot21)^2\\cdot21=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d5d\/2f3\/43f\/d5d2f343f7cc280ba9de8683d46e51df.svg\" width=\"194\" height=\"25\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=(194 481\\cdot21)^2\\cdot21=\" alt=\"=(194 481\\cdot21)^2\\cdot21=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/493\/647\/9a3\/4936479a3ed3603b6b09362550b5b69b.svg\" width=\"192\" height=\"25\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=4084101^2\\cdot21=\" alt=\"=4084101^2\\cdot21=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/28b\/685\/0cc\/28b6850cc117feb61f73202f75e40f4b.svg\" width=\"152\" height=\"21\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=350277500542221\" alt=\"=350277500542221\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/91c\/759\/7e6\/91c7597e6330d2fd245c4b1625e7f418.svg\" width=\"168\" height=\"17\"\/><\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432 Python<\/p>\n<pre><code>def my_power(val, p):     res, v, c = 1, val, p     if c &amp;1:         res = v     c>>=1         while c>0:         v = v * v        if c&amp;1:             res = v*res        c = c>>1     return res<\/code><\/pre>\n<p>\u0438\u043b\u0438<\/p>\n<pre><code>def my_power(val, p):     res, v, c = 1, val, p     bin_k = list(map(int,bin(p)[2:]))     for i in range(len(bin_k)):         res = res * res         if bin_k[i] == 1:             res = res*v     return res  <\/code><\/pre>\n<h3>\u0421\u0445\u0435\u043c\u0430 \u00ab\u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e\u00bb<\/h3>\n<p>\u0417\u0434\u0435\u0441\u044c, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0441\u0445\u0435\u043c\u044b \u00ab\u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e\u00bb \u0431\u0438\u0442\u044b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043e\u0442 \u043c\u043b\u0430\u0434\u0448\u0435\u0433\u043e \u043a \u0441\u0442\u0430\u0440\u0448\u0435\u043c\u0443.<\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c<\/p>\n<ol>\n<li>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043a\u043e\u0434\u0435.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0432\u0435\u0441\u0442\u0438 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e y \u0440\u0430\u0432\u043d\u043e\u0439 \u0447\u0438\u0441\u043b\u0443 x.<\/p>\n<\/li>\n<li>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 i \u0438 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043e\u0442 0 \u0434\u043e k-1.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i =1, \u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0443\u043c\u043d\u043e\u0436\u0430\u0435\u0442\u0441\u044f \u043d\u0430 y, \u0430 \u0441\u0430\u043c\u043e \u0447\u0438\u0441\u043b\u043e y \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=0, \u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 y \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.\u00a0<\/p>\n<\/li>\n<\/ol>\n<p>\u0414\u0430\u043d\u043d\u0430\u044f \u0441\u0445\u0435\u043c\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0436\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438 \u0441\u0445\u0435\u043c\u0430 \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e.<\/p>\n<p>\u0412, \u043e\u0431\u0449\u0435\u043c \u0432\u0438\u0434\u0435 \u0441\u0445\u0435\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x^n=x^\\color{red}{m_0}\\cdot(x^2)^\\color{purple}{m_1{}}\\cdot({x^{2^2}})^{\\color{blue}m_2}\\cdot...\\cdot(x^{2^k})^\\color{green}{m_k}\" alt=\"x^n=x^\\color{red}{m_0}\\cdot(x^2)^\\color{purple}{m_1{}}\\cdot({x^{2^2}})^{\\color{blue}m_2}\\cdot...\\cdot(x^{2^k})^\\color{green}{m_k}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bab\/518\/747\/bab518747cad339607649bc81b0b13e7.svg\" width=\"325\" height=\"28\"\/><\/p>\n<p>\u0438\u043b\u0438<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x^n=\\prod\\limits_{i=0}^k(a^{2^i})^{m_i}\" alt=\"x^n=\\prod\\limits_{i=0}^k(a^{2^i})^{m_i}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ef6\/a68\/595\/ef6a6859596f3a972c670dad9142106c.svg\" width=\"131\" height=\"61\"\/><\/p>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432\u0448\u0438\u0441\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u043c <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"21^{11}\" alt=\"21^{11}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ebd\/3b2\/296\/ebd3b2296f59f3d14cb1c7ca50a0fb7b.svg\" width=\"35\" height=\"21\"\/><\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"m_\\color{red}{m_0} = 1, \\color{purple}{m_1} =1, \\color{blue}{m_2} = 0, \\color{green}{m_3} = 1\" alt=\"m_\\color{red}{m_0} = 1, \\color{purple}{m_1} =1, \\color{blue}{m_2} = 0, \\color{green}{m_3} = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/227\/a61\/63c\/227a6163c3048f94b5493ec152f1a164.svg\" width=\"285\" height=\"22\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"21^{11}=21^{\\color{red}{m_0}}\\cdot(21^2){^{\\color{purple}{m_1}}}\\cdot(21^{2^2}){^{\\color{blue}{m_2}}}\\cdot(21^{2^{2^2}})^\\color{green}{m_3}=\" alt=\"21^{11}=21^{\\color{red}{m_0}}\\cdot(21^2){^{\\color{purple}{m_1}}}\\cdot(21^{2^2}){^{\\color{blue}{m_2}}}\\cdot(21^{2^{2^2}})^\\color{green}{m_3}=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bf7\/942\/4c4\/bf79424c4dc0821cab2b089552fb410b.svg\" width=\"375\" height=\"31\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=21^\\color{red}{1}\\cdot(21^2){^\\color{purple}{1}}\\cdot(21^{2^2}){^\\color{blue}{0}}\\cdot(21^{2^{2^2}})^\\color{green}{1}=\" alt=\"=21^\\color{red}{1}\\cdot(21^2){^\\color{purple}{1}}\\cdot(21^{2^2}){^\\color{blue}{0}}\\cdot(21^{2^{2^2}})^\\color{green}{1}=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4a4\/7a3\/655\/4a47a3655aeb2ab3738b8a1fd97beb45.svg\" width=\"288\" height=\"31\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=21^{11}=21\\cdot21^2\\cdot21^{2^{2^2}}=21\\cdot441\\cdot37822859361=\" alt=\"=21^{11}=21\\cdot21^2\\cdot21^{2^{2^2}}=21\\cdot441\\cdot37822859361=\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d14\/2a7\/31b\/d142a731b3da0b1d2cfe951ab8488461.svg\" width=\"431\" height=\"27\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"=9261\\cdot37822859361=350277500542221\" alt=\"=9261\\cdot37822859361=350277500542221\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bbd\/193\/4e1\/bbd1934e12c9784dcc75af81b48abfe8.svg\" width=\"355\" height=\"17\"\/><\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432 Python<\/p>\n<pre><code>def fast_pow(val, p):     s, v,c =1,val,p     while (c!=0):         if (c %2==1):             s = s* v         c = c>>1           v = v*v     return s<\/code><\/pre>\n<h3>\u041b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 \u041c\u043e\u043d\u0442\u0433\u043e\u043c\u0435\u0440\u0438<\/h3>\n<p>\u0414\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0447\u0430\u0441\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0435\u0442 \u0437\u0430\u0449\u0438\u0442\u0443 \u043e\u0442 \u0430\u043a\u0442\u0430\u043a \u043f\u043e \u043f\u043e\u0431\u043e\u0447\u043d\u044b\u043c \u043a\u0430\u043d\u0430\u043b\u0430\u043c \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u043e\u0441\u0442\u0438. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0431\u0438\u0442\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u0432 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 0 \u0438\u043b\u0438 1. \u042d\u0442\u043e \u0434\u0430\u0435\u0442 \u0442\u043e, \u0447\u0442\u043e \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0440\u0430\u0437\u043d\u044b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0438 \u0438\u0437\u0432\u043d\u0435 \u0441\u043b\u043e\u0436\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u044c \u0447\u0442\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442.<\/p>\n<p>\u0414\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0445 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c n \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c.<\/p>\n<ol>\n<li>\n<p>\u0412\u0432\u0435\u0441\u0442\u0438 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 <\/p>\n<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1 \u0438 x_2. x_1=x, x_2=x^2\" alt=\"x_1 \u0438 x_2. x_1=x, x_2=x^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2b1\/82f\/525\/2b182f525dc967a9013c55ca59be1286.svg\" width=\"190\" height=\"28\"\/><\/p>\n<ol>\n<li>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 i \u0438 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043e\u0442 k-1 \u0434\u043e 0.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=0, \u0442\u043e\u0433\u0434\u0430 <\/p>\n<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_2=x_1\\cdot{x_2}, x_1=x^2_1\" alt=\"x_2=x_1\\cdot{x_2}, x_1=x^2_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b33\/145\/235\/b33145235e836861442c3b16f5b39e71.svg\" width=\"175\" height=\"25\"\/><\/p>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=1, \u0442\u043e\u0433\u0434\u0430 <\/p>\n<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1=x_1\\cdotx_2, x_2=x^2_2\" alt=\"x_1=x_1\\cdotx_2, x_2=x^2_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f2b\/b58\/275\/f2bb5827551e5f8c7b99b37fd112d630.svg\" width=\"207\" height=\"25\"\/><\/p>\n<ol>\n<li>\n<p>\u0412 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 x_1 \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 x \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c n.<\/p>\n<\/li>\n<\/ol>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 (\u043e\u0442 \u0434\u043e log n): \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0438\u043c\u0435\u044e\u0442 \u043c\u0435\u0441\u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0431\u0438\u0442\u0430.<\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 21 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c 11. \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"11_{10}=\\color{green}{1}\\color{blue}{0}\\color{purple}{1}\\color{red}{1}_2\" alt=\"11_{10}=\\color{green}{1}\\color{blue}{0}\\color{purple}{1}\\color{red}{1}_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6d4\/5a3\/196\/6d45a31965fc700fe595b6d95e5862d4.svg\" width=\"110\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1=1, x_2=21\" alt=\"x_1=1, x_2=21\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cf4\/55d\/194\/cf455d194a6f547dc21e75f82eff13b3.svg\" width=\"130\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{green}{m_3}=1\" alt=\"\\color{green}{m_3}=1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/038\/795\/7e3\/0387957e399e6feeee160f1d0b726446.svg\" width=\"62\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1=21\\cdot1=21, x_2 = 21^2=441\" alt=\"x_1=21\\cdot1=21, x_2 = 21^2=441\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/230\/3d4\/7b9\/2303d47b92c970c8874974704fc5764b.svg\" width=\"274\" height=\"24\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{blue}{m_2} = 0\" alt=\"\\color{blue}{m_2} = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/728\/511\/33f\/72851133f48641efb5538b294bdb4df7.svg\" width=\"62\" height=\"19\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_2 = 21\\cdot441=9261\" alt=\"x_2 = 21\\cdot441=9261\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0d7\/fec\/c16\/0d7fecc1634f623a1fc4575e81138e71.svg\" width=\"175\" height=\"19\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1=21^2=441\" alt=\"x_1=21^2=441\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dbc\/058\/bdc\/dbc058bdcbf8f045d116dff2881bff07.svg\" width=\"130\" height=\"23\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{purple}{m_1} = 1\" alt=\"\\color{purple}{m_1} = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/94e\/8cf\/8ce\/94e8cf8cec42d6e8197dfaed7917b39e.svg\" width=\"62\" height=\"19\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1 = 441cdot9261=4084101\" alt=\"x_1 = 441cdot9261=4084101\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/af7\/742\/ef4\/af7742ef4274548a783c4f9b2d1f7976.svg\" width=\"245\" height=\"19\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_2 = 9261^2 = 85766121\" alt=\"x_2 = 9261^2 = 85766121\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c00\/5a0\/c80\/c005a0c80b763dfd71d081ad40c0a054.svg\" width=\"199\" height=\"23\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\color{red}{m_0} = 1\" alt=\"\\color{red}{m_0} = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/213\/d25\/80e\/213d2580e71a961a68864e4d841af5c4.svg\" width=\"62\" height=\"20\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_1=4084101cdot85766121 = 350277500542221\" alt=\"x_1=4084101cdot85766121 = 350277500542221\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a19\/cec\/04a\/a19cec04a15f246bb71949ff7c2e2680.svg\" width=\"401\" height=\"19\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x_2=85766121^2\" alt=\"x_2=85766121^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb8\/8bf\/04b\/eb88bf04b1f45f97c5c71a3c0ad2d5c7.svg\" width=\"133\" height=\"23\"\/><\/p>\n<ol start=\"6\">\n<li>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 <\/p>\n<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"21^{11} = 350277500542221\" alt=\"21^{11} = 350277500542221\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9cb\/44a\/fbd\/9cb44afbd73476efc38a2065b8bb9043.svg\" width=\"208\" height=\"21\"\/><\/p>\n<pre><code>def powers(val,p):     x1 = 1     x2 = val     bin_k = list(map(int,bin(p)[2:]))         for i in range(len(bin_k)):             if bin_k[i]==0:             x2 = x1*x2             x1 = x1*x1             else:             x1 = x1*x2             x2 = x2*x2        return x1<\/code><\/pre>\n<h3>\u041c\u0435\u0442\u043e\u0434 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435\u0439<\/h3>\n<p>\u0414\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0432\u0438\u0434\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435\u0439. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435\u0439 \u0438 \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432 \u043a\u0430\u0436\u0434\u0443\u044e \u0438\u0437 \u043d\u0438\u0445. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0414\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0448\u0438\u0440\u043e\u043a\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0435\u0439 \u0438 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0445, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438. \u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u043b\u044e\u0431\u043e\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u043b\u043e\u0436\u0438\u0442\u044c \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0438 \u0442\u0430\u043a\u043e\u0435 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0435\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"11 = 11^1\" alt=\"11 = 11^1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/230\/71d\/ad5\/23071dad5e7ef29db1ea8552ea521d7d.svg\" width=\"74\" height=\"21\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"100=2\\cdot2\\cdot5\\cdot5=2^2\\cdot5^2\" alt=\"100=2\\cdot2\\cdot5\\cdot5=2^2\\cdot5^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e9c\/5bd\/b03\/e9c5bdb03a73802a630e97f7c78ef88a.svg\" width=\"215\" height=\"21\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"126=2\\cdot3\\cdot3\\cdot7 = 2^1\\cdot3^2\\cdot7^1\" alt=\"126=2\\cdot3\\cdot3\\cdot7 = 2^1\\cdot3^2\\cdot7^1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b39\/f0e\/e27\/b39f0ee2775e5972d7eea09721518a81.svg\" width=\"247\" height=\"21\"\/><\/p>\n<p>\u0420\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 \u0432 \u043e\u0431\u0449\u0435\u043c \u0432\u0438\u0434\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0442\u0430\u043a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"n=p^{a_1}_1\\cdot{p^{a_2}_2}\\cdot...\\cdot{p^{a_k}_k}\" alt=\"n=p^{a_1}_1\\cdot{p^{a_2}_2}\\cdot...\\cdot{p^{a_k}_k}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1cd\/230\/61a\/1cd23061a5cdadb00d40a752f8310f72.svg\" width=\"165\" height=\"25\"\/><\/p>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u043b\u043e\u0436\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u043d\u0430 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u0435\u043b\u0435\u0442\u0435\u043b\u0435\u0439. \u0411\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u043e\u0442 2 \u0434\u043e \u043a\u043e\u0440\u043d\u044f \u0438\u0437 n \u0438 \u0435\u0441\u043b\u0438 n \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 \u044d\u0442\u043e\u0442 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u0431\u0443\u0434\u0435\u043c \u043d\u0430 \u043d\u0435\u0433\u043e \u0434\u0435\u043b\u0438\u0442\u044c. \u0418 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437. \u0422\u0430\u043a \u043c\u044b \u0441\u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0431\u0440\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438 \u0438 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u0432 \u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442, \u043a\u043e\u0433\u0434\u0430 n \u0441\u0442\u0430\u043d\u0435\u0442 \u043b\u0438\u0431\u043e 1, \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c.<\/p>\n<pre><code>def factorize(n):     factors = []     i =2     while i*i&lt;=n: # \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c         while n%i==0: # \u043f\u043e\u043a\u0430 n \u043d\u0430 \u043d\u0435\u0433\u043e \u0434\u0435\u043b\u0438\u0442\u0441\u044f         n\/\/=i # \u0434\u0435\u043b\u0438\u043c \u043d\u0430 \u044d\u0442\u043e\u0442 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c         factors.append(i)     i +=1 # \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e n \u0441\u0442\u0430\u043b\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0447\u0438\u0441\u043b\u043e\u043c # \u0438 \u0435\u0433\u043e \u0442\u043e\u0436\u0435 \u043d\u0430\u0434\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435             if n>1:             factors.append(n)     return factors<\/code><\/pre>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/p>\n<pre><code>def power_fact(n,p):     lists = factorize(p)     result = n     for el in lists:         result = result**el     return result<\/code><\/pre>\n<h3>\u0411\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430<\/h3>\n<p>\u0421\u043a\u043e\u0440\u0435\u0435 \u0431\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u043d\u0435 \u0441\u043e\u0432\u0441\u0435\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0431\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u043d\u043e \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u0441\u0442\u0430\u0442\u044c\u0438 \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c. \u0411\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u043e\u0439 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0441\u0443\u043c\u043c\u044b \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d. \u0422\u043e \u0435\u0441\u0442\u044c \u043e\u043d \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b, \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0432 \u043b\u044e\u0431\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u041c\u0430\u0433\u0438\u044f \u0411\u0438\u043d\u043e\u043c\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0435 \u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438.<\/p>\n<p>\u0418\u0437 \u0443\u0440\u043e\u043a\u043e\u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u043c\u044b \u0432\u0441\u0435 \u043f\u043e\u043c\u043d\u0438\u043c \u0442\u0430\u043a\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b)^2=a^2+2ab+b^2\" alt=\"(a+b)^2=a^2+2ab+b^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c6\/1e3\/105\/4c61e310575d74775bf46582b1a4ac33.svg\" width=\"206\" height=\"25\"\/><\/p>\n<p>\u0418 \u044d\u0442\u043e \u0442\u043e\u0436\u0435 \u0431\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430, \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 \u0435\u0433\u043e \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439.<\/p>\n<p>\u0412 \u043e\u0431\u0449\u0435\u043c \u0432\u0438\u0434\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0432\u0438\u0434<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b)^n=C^0_n\\cdot{a^n}+C^1_n\\cdot{a^{n-1}}\\cdot{b}+...+C^{n-1}n\\cdot{a}\\cdot{b^{n-1}}+C^n_n\\cdot{b^n}\" alt=\"(a+b)^n=C^0_n\\cdot{a^n}+C^1_n\\cdot{a^{n-1}}\\cdot{b}+...+C^{n-1}n\\cdot{a}\\cdot{b^{n-1}}+C^n_n\\cdot{b^n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/96c\/dac\/eca\/96cdaceca1e2be203d35618bb6c09303.svg\" width=\"545\" height=\"25\"\/><\/p>\n<p>\u0438\u043b\u0438<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b)^n=\\sum{k=0}^{n}C_n^k\\cdot{a^{n-k}}\\cdot{b^k}\" alt=\"(a+b)^n=\\sum{k=0}^{n}C_n^k\\cdot{a^{n-k}}\\cdot{b^k}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/063\/253\/9d2\/0632539d22f3bec6acd9fe9bb1bbc62b.svg\" width=\"291\" height=\"30\"\/><\/p>\n<p>\u0447\u0438\u0441\u043b\u0430 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\u0421^n_m\" alt=\"\u0421^n_m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/214\/730\/70d\/21473070d56728f53ba38f8e6abbeebb.svg\" width=\"25\" height=\"29\"\/><\/p>\n<p> \u2014 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"C^m_n=\\frac{n!}{m!(n-m)!}\" alt=\"C^m_n=\\frac{n!}{m!(n-m)!}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d0d\/b9f\/f2d\/d0db9ff2d0674702420905f3944e0a7c.svg\" width=\"159\" height=\"49\"\/><\/p>\n<p> \u2014 \u0447\u0438\u0441\u043b\u043e \u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u0439 \u0438\u0437 n \u043f\u043e m.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"C^0_n=1, C^n_n=1\" alt=\"C^0_n=1, C^n_n=1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/80b\/2cd\/c11\/80b2cdc112f707d4829b9d5ad7526135.svg\" width=\"130\" height=\"23\"\/><\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0434\u043b\u044f \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u0431\u0438\u043d\u043e\u043c\u0430 \u043d\u0430\u043c \u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437 \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b, \u0442\u043e \u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0434\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430. \u0410 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u044b \u0432 \u0441\u0438\u043b\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0435\u0434\u044f\u0442 \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438. \u041c\u043e\u0436\u0435\u0442 \u0442\u0430\u043a \u0441\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u043f\u0440\u0438 \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u043e\u0432 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u0441\u044f \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0430\u044f \u043f\u0430\u043c\u044f\u0442\u044c. \u0418 \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0430 \u043f\u043e\u043c\u043e\u0449\u044c \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u041f\u0430\u0441\u043a\u0430\u043b\u044f.\u00a0<\/p>\n<p>\u0422\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u041f\u0430\u0441\u043a\u0430\u043b\u044f \u2014 \u044d\u0442\u043e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u0430\u0436\u0434\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0440\u0430\u0432\u043d\u043e \u0441\u0443\u043c\u043c\u0435 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u043d\u0430\u0434 \u043d\u0438\u043c. \u041d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0438 \u043f\u043e \u0440\u0435\u0431\u0440\u0430\u043c \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u044b \u0435\u0434\u0438\u043d\u0438\u0446\u044b. \u0421\u0442\u0440\u043e\u043a\u0438 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u0441\u0438.\u00a0 \u0422\u0430\u043a\u043e\u0439 \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0442\u044c \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e.<\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f n=4<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/17f\/d16\/145\/17fd1614515f6d7613699b4d036f14ea.png\" width=\"670\" height=\"333\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/17f\/d16\/145\/17fd1614515f6d7613699b4d036f14ea.png\"\/><\/figure>\n<p>\u0422\u043e\u0433\u0434\u0430 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0431\u0438\u043d\u043e\u043c<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(x+y)^\\color{blue}{4}=\\color{red}{1}x^\\color{blue}{4}+\\color{green}{4}x^\\color{blue}{3}y\\color{blue}{^1}+\\color{purple}{6}x^\\color{blue}{2}y^\\color{blue}{2}+\\color{green}{4}x^\\color{blue}{1}y^\\color{blue}{3}+\\color{red}{1}y^\\color{blue}{4}\" alt=\"(x+y)^\\color{blue}{4}=\\color{red}{1}x^\\color{blue}{4}+\\color{green}{4}x^\\color{blue}{3}y\\color{blue}{^1}+\\color{purple}{6}x^\\color{blue}{2}y^\\color{blue}{2}+\\color{green}{4}x^\\color{blue}{1}y^\\color{blue}{3}+\\color{red}{1}y^\\color{blue}{4}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f0f\/8d9\/aa1\/f0f8d9aa10c8599f4fab4b4685fc042e.svg\" width=\"0\" height=\"0\"\/><\/p>\n<p>\u0418\u0437 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0441\u0443\u043c\u043c\u0430 \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439 \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0432\u043d\u0430 n, \u0430 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b.<\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0430\u043a\u043e\u0433\u043e \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0439\u0442\u0438\u0441\u044c \u0431\u0435\u0437 \u0432\u0441\u0435\u0445 \u044d\u0442\u0438\u0445 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u043e\u0432, \u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u00a0 \u0431\u044b\u0441\u0442\u0440\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043d\u0443\u0436\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b, \u043f\u043e\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0438\u0445 \u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0431\u0438\u043d\u043e\u043c\u0430 \u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u043e\u0442\u0432\u0435\u0442.\u00a0<\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0431\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432 \u0437\u0430\u0434\u0430\u043d\u043d\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0440\u0430\u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044f \u0438\u0445 \u043d\u0430 \u0441\u0443\u043c\u043c\u0443 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b \u043f\u043e\u043c\u0435\u043d\u044c\u0448\u0435, \u0430 \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0435 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u0431\u0438\u043d\u043e\u043c. \u0422\u0430\u043a\u0436\u0435 \u0431\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u0438\u043a\u043e\u0439 \u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044f\u043c\u0438. \u0411\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0447\u0430\u0441\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u0445 \u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u0445 \u0441 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c, \u0430 \u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u0445 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u044b \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435 \u043d\u0435\u0439\u0440\u043e\u043d\u043d\u044b\u0435 \u0441\u0435\u0442\u0438.<\/p>\n<p>\u041d\u0430\u0439\u0434\u0435\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0432 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0411\u0438\u043d\u043e\u043c\u0430<\/p>\n<pre><code>def my_binom(n):     res=[1]     for i in range(n):         res=[1]+[res[i]+res[i+1] for i in range(len(res)-1)]+[1]     return res<\/code><\/pre>\n<p>\u0418 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0438\u043d\u043e\u043c\u0430<\/p>\n<pre><code>def binoms(a,b,n):     res = 0     k = 0     koef = my_binom(n)     while k&lt;= n:         res = res+koef[k]*a**(n-k)*b**k         k = k+1     return res<\/code><\/pre>\n<p>\u0417\u0430 \u0440\u0430\u043c\u043a\u0430\u043c\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u043e\u0441\u0442\u0430\u043b\u0438\u0441\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0435\u0449\u0435 \u0431\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c\u0438, \u0447\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u041a \u043d\u0438\u043c \u043c\u043e\u0436\u043d\u043e \u043e\u0442\u043d\u0435\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c \u00ab\u043c\u0435\u0442\u043e\u0434 \u043e\u043a\u043d\u0430\u00bb, \u00ab\u043c\u0435\u0442\u043e\u0434 \u0441\u043a\u043e\u043b\u044c\u0437\u044f\u0449\u0435\u0433\u043e \u043e\u043a\u043d\u0430\u00bb. \u0421\u043c\u044b\u0441\u043b \u044d\u0442\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0435 \u043e\u0434\u0438\u043d, \u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0431\u0438\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u00a0 \u043c\u043e\u0436\u043d\u043e \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0448\u0438\u0440\u0438\u043d\u0443 \u043e\u043a\u043d\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0445 \u0431\u0438\u0442\u043e\u0432.<\/p>\n<p>\u041a\u0430\u043a \u0435\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u0415\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u043e\u0434\u043d\u043e \u0438 \u0442\u043e\u0436\u0435 \u0447\u0438\u0441\u043b\u043e \u0432 \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u0440\u0435\u0434\u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043a \u043d\u0435\u0439 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443. \u0422\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c \u0443\u0436\u0435 \u0441\u0434\u0435\u043b\u0430\u043d\u043d\u044b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 Pyton \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u0435\u043a\u043e\u0440\u0430\u0442\u043e\u0440 <a class=\"mention\" href=\"\/users\/lru_cache\">@lru_cache<\/a> \u0438\u0437 \u043c\u043e\u0434\u0443\u043b\u044f functools. \u0415\u0441\u043b\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043a\u043e\u043c\u043f\u043b\u0435\u043a\u0441\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u0442\u043e\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>cmath.exp()<\/code>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442 \u0435\u0433\u043e \u0432 \u0437\u0430\u0434\u0430\u043d\u043d\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0422\u0430\u043a\u0436\u0435 \u0432\u0430\u0436\u043d\u043e \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u044f\u0437\u044b\u043a\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b.<\/p>\n<blockquote>\n<p>\u041c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d \u0434\u043b\u044f \u0431\u0443\u0434\u0443\u0449\u0438\u0445 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u0432 \u043e\u043d\u043b\u0430\u0439\u043d-\u043a\u0443\u0440\u0441\u0430 OTUS <a href=\"https:\/\/otus.pw\/Ww0l\/\">\u00ab\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u0434\u043b\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432\u00bb<\/a>. 13 \u0434\u0435\u043a\u0430\u0431\u0440\u044f \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u043a\u0443\u0440\u0441\u0430 \u043f\u0440\u043e\u0439\u0434\u0435\u0442 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0443\u0440\u043e\u043a \u00ab\u0420\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0441\u0432\u043e\u0435\u0433\u043e \u044f\u0437\u044b\u043a\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e ANTLR\u00bb, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u0433\u043b\u0430\u0448\u0430\u0435\u043c \u0432\u0441\u0435\u0445 \u0436\u0435\u043b\u0430\u044e\u0449\u0438\u0445. \u041d\u0430 \u0437\u0430\u043d\u044f\u0442\u0438\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0441\u0438\u043d\u0442\u0430\u043a\u0441\u0438\u0441 \u0438 \u0441\u0435\u043c\u0430\u043d\u0442\u0438\u043a\u0443 \u0422\u044c\u044e\u0440\u0438\u043d\u0433-\u043f\u043e\u043b\u043d\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0417\u0430\u043f\u0438\u0441\u0430\u0442\u044c\u0441\u044f \u043c\u043e\u0436\u043d\u043e <a href=\"https:\/\/otus.pw\/2aVN\/\">\u0437\u0434\u0435\u0441\u044c.<\/a><\/p>\n<\/blockquote>\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\/779396\/\"> https:\/\/habr.com\/ru\/articles\/779396\/<\/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><em>\u0410\u0432\u0442\u043e\u0440 \u0441\u0442\u0430\u0442\u044c\u0438 \u2014 \u0412\u0438\u043a\u0442\u043e\u0440\u0438\u044f \u041b\u044f\u043b\u0438\u043a\u043e\u0432\u0430<\/em><\/p>\n<p>\u0412 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043c\u044b \u0443\u0436\u0435 \u0442\u0430\u043a \u043f\u0440\u0438\u0432\u044b\u043a\u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0433\u043e\u0442\u043e\u0432\u044b\u043c\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c\u0438, \u0447\u0442\u043e \u043f\u0440\u0438 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0438 \u0432\u044b\u0441\u043e\u043a\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e\u0433\u043e \u043a\u043e\u0434\u0430, \u0434\u0430\u0436\u0435 \u043d\u0435 \u0437\u0430\u0434\u0443\u043c\u044b\u0432\u0430\u0435\u043c\u0441\u044f \u043d\u0430\u0434 \u0442\u0435\u043c, \u0430 \u043a\u0430\u043a \u0432\u043e\u043e\u0431\u0449\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b \u0442\u0435 \u0438\u043b\u0438 \u0438\u043d\u044b\u0435 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u044b. \u0418 \u0443\u0436 \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0447\u0438\u0441\u0435\u043b \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u043c\u044b \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u0437\u0430\u0434\u0443\u043c\u044b\u0432\u0430\u0435\u043c\u0441\u044f \u043e \u0442\u043e\u043c, \u0430 \u043a\u0430\u043a \u0432\u043e\u043e\u0431\u0449\u0435 \u0432\u0441\u0435 \u044d\u0442\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e. \u0418 \u043a\u0430\u043a\u0438\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e?<\/p>\n<p>\u0412\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0435. \u0427\u0442\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u0442\u0430\u043a\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c? \u041a\u0430\u043a \u043d\u0430\u043c \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e \u0435\u0449\u0435 \u0441\u043e \u0448\u043a\u043e\u043b\u044b \u2014 \u044d\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u0441\u0435\u0431\u044f. \u041d\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043a\u0440\u043e\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438.<\/p>\n<p>\u041c\u043d\u043e\u0433\u0438\u0435 \u0438\u0437 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c n \u0447\u0438\u0441\u043b\u0430 x \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0442\u044c x \u043d\u0430 \u0441\u0430\u043c\u043e \u0441\u0435\u0431\u044f n \u0440\u0430\u0437, \u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u0443\u0436\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438. \u0422\u0430\u043a\u0436\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0446\u0438\u0444\u0440\u044b \u0432 \u0441\u043e\u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u044e\u0442\u0441\u044f. \u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b.\u00a0<\/p>\n<p>\u0417\u0430\u0447\u0435\u043c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c?<strong> <\/strong>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043e\u043f\u0435\u0440\u0438\u0440\u0443\u044e\u0442 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0434\u043b\u0438\u043d\u043e\u0439 \u0432 \u0442\u044b\u0441\u044f\u0447\u0438 \u0431\u0438\u0442. \u0412 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u0438 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043c\u043e\u0434\u0435\u043b\u0435\u0439: \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445, \u043d\u0435\u0439\u0440\u043e\u0441\u0435\u0442\u0435\u0432\u044b\u0445, \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u0438 \u0434\u0440. \u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0434\u043b\u044f \u0437\u0430\u0449\u0438\u0442\u044b \u043f\u0430\u0440\u043e\u043b\u0435\u0439 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u043a\u043e\u043d\u0444\u0438\u0434\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0442\u043e\u0436\u0435 \u043d\u0435 \u043e\u0431\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0431\u0435\u0437 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0418 \u044d\u0442\u043e\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0442\u044c \u0434\u0430\u043b\u044c\u0448\u0435. \u041c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432.<\/p>\n<h3>\u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/h3>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0447\u0435\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 x \u0438 n \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043c\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0435 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e<\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0437\u0430 \u043e\u0434\u043d\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0441\u0432\u0435\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0432\u0434\u0432\u043e\u0435 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438.<\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0447\u0435\u0442\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0435<\/p>\n<p>\u0415\u0441\u043b\u0438 n \u043d\u0435\u0447\u0435\u0442\u043d\u0430, \u0442\u043e\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0441\u0442\u0435\u043f\u0435\u043d\u0438 (n-1),\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0443\u0436\u0435 \u0431\u0443\u0434\u0435\u0442 \u0447\u0435\u0442\u043d\u043e\u0439.<\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0440\u0435\u043a\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430: \u043e\u0442 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u043c\u044b \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 \u0447\u0435\u0442\u043d\u0430<\/p>\n<p>\u0430 \u0438\u043d\u0430\u0447\u0435 \u2014 <\/p>\n<p>\u0418 \u0442\u043e\u0433\u0434\u0430 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c m \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u0442\u043e\u0447\u043d\u0435\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.<\/p>\n<p>\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u043c \u044d\u0442\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0435 \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u0435 \u043d\u0430 \u043e\u0431\u0449\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439, \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432\u0448\u0438\u0441\u044c \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e\u043c<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n&lt;0, \u0442\u043e\u0433\u0434\u0430<\/p>\n<p>\u0412\u0441\u0435\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 2logn \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432, \u043f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043c\u044b \u043f\u0440\u0438\u0434\u0435\u043c \u043a n=0. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u0437\u0430 O(log n) \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439.<\/p>\n<p>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u043e\u0439, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 <\/p>\n<p>\u0433\u0434\u0435<\/p>\n<p>\u0438 <\/p>\n<p>\u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043d\u0443\u043b\u0435\u0439 \u0438 \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u0447\u0438\u0441\u043b\u0430 n. \u042d\u0442\u0430 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0430 \u0440\u0430\u0441\u0442\u0435\u0442 \u043a\u0440\u0430\u0439\u043d\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0441 \u0440\u043e\u0441\u0442\u043e\u043c n.<\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u043d\u0430\u043c \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432 10000000000-\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u0442\u043e \u043c\u044b \u043e\u0431\u043e\u0448\u043b\u0438\u0441\u044c \u0431\u044b \u0432\u0441\u0435\u0433\u043e 43 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f\u043c\u0438. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0438\u0442\u043c<\/p>\n<pre><code>def my_power(val,p):     if p&lt;0:         return my_power(1\/val, -p)     if p==0:         return 1     if p%2 == 0:         return my_power(val*val, p\/2)     else:         return val*power(val*val,(p-1)\/2)<\/code><\/pre>\n<p>\u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u043c \u0432\u044b\u0437\u043e\u0432\u0435 \u0432 \u044d\u0442\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f \u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0446\u0438\u0444\u0440\u044b \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n. \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0431\u0438\u0442\u043e\u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f n. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432 \u0440\u0430\u0432\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 1 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 n.<\/p>\n<p>\u041d\u043e \u0435\u0441\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u043e\u0435 \u0441 \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u043c \u043e\u0431\u044a\u0435\u043c\u043e\u043c \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u0435\u043d \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u2014 \u0438\u043b\u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u0435\u0441\u043b\u0438 \u043e\u0431\u044a\u0435\u043c \u043d\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f.<\/p>\n<h3>\u0411\u0438\u043d\u0430\u0440\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/h3>\n<p>\u041e\u0434\u0438\u043d \u0438\u0437 \u0441\u0430\u043c\u044b\u0445 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0414\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438. \u0417\u0430 \u0441\u0447\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438, \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f, \u0432\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435 \u0447\u0435\u0433\u043e \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f. \u0422\u0430\u043a\u0436\u0435 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043f\u0440\u0438 \u043b\u044e\u0431\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>\u0421\u0443\u0442\u044c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044c, \u0432 \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 \u0447\u0438\u0441\u043b\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u0432\u0438\u0434\u0435. \u0418 \u0434\u0430\u043b\u0435\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u0431\u0438\u0442\u0430\u043c \u044d\u0442\u043e\u0433\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430. \u0422\u0430\u043a\u043e\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u0442\u0441\u044f \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0431\u0438\u0442\u044b \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b.\u00a0<\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0435 \u0441\u0445\u0435\u043c\u0443 \u201c\u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e\u201d \u0438 \u0441\u0445\u0435\u043c\u0443 \u201c\u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e\u201d. \u0414\u043b\u044f \u0432\u0441\u0435\u0445 \u044d\u0442\u0438\u0445 \u0441\u0445\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e \u0438 \u0440\u0430\u0432\u043d\u043e k, \u0433\u0434\u0435 k \u2014 \u0434\u043b\u0438\u043d\u0430 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 n \u0431\u0438\u0442\u0430\u0445, <\/p>\n<p>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0436\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u0447\u0438\u0441\u043b\u0430 n. \u0412 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <\/p>\n<p>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0432 \u0441\u043e\u0442\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u044d\u0442\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c 8 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442. \u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043f\u0440\u0438 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f n-1 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f, \u0442\u043e \u0435\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0446\u0435\u043d\u0435\u043d\u043e \u043a\u0430\u043a O(n).<\/p>\n<h2>\u0421\u0445\u0435\u043c\u0430 \u00ab\u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e\u00bb<\/h2>\n<p>\u041d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u0441\u0430\u043c\u043e \u0437\u0430 \u0441\u0435\u0431\u044f, \u0432 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u0435 \u0431\u0438\u0442\u044b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u0442 \u0441\u0442\u0430\u0440\u0448\u0435\u0433\u043e \u043a \u043c\u043b\u0430\u0434\u0448\u0435\u043c\u0443.<\/p>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u044c n \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435<\/p>\n<p>\u0422\u043e\u0433\u0434\u0430<\/p>\n<p>\u0433\u0434\u0435 <\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 \u0447\u0438\u0441\u043b\u043e x \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0442\u0430\u043a<\/p>\n<p>\u0418 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c<\/p>\n<ol>\n<li>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043a\u043e\u0434\u0435.<\/p>\n<\/li>\n<li>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 i \u0438 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043e\u0442 k-1 \u0434\u043e 0.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=1, \u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0438 \u0437\u0430\u0442\u0435\u043c \u0443\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u043d\u0430 \u0445.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=0, \u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.\u00a0<\/p>\n<\/li>\n<\/ol>\n<p>\u0418\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a<\/p>\n<p>\u041f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0432 <\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432 Python<\/p>\n<pre><code>def my_power(val, p):     res, v, c = 1, val, p     if c &amp;1:         res = v     c>>=1         while c>0:         v = v * v        if c&amp;1:             res = v*res        c = c>>1     return res<\/code><\/pre>\n<p>\u0438\u043b\u0438<\/p>\n<pre><code>def my_power(val, p):     res, v, c = 1, val, p     bin_k = list(map(int,bin(p)[2:]))     for i in range(len(bin_k)):         res = res * res         if bin_k[i] == 1:             res = res*v     return res  <\/code><\/pre>\n<h3>\u0421\u0445\u0435\u043c\u0430 \u00ab\u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e\u00bb<\/h3>\n<p>\u0417\u0434\u0435\u0441\u044c, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0441\u0445\u0435\u043c\u044b \u00ab\u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e\u00bb \u0431\u0438\u0442\u044b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u0440\u043e\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043e\u0442 \u043c\u043b\u0430\u0434\u0448\u0435\u0433\u043e \u043a \u0441\u0442\u0430\u0440\u0448\u0435\u043c\u0443.<\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c<\/p>\n<ol>\n<li>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 n \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043a\u043e\u0434\u0435.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0432\u0435\u0441\u0442\u0438 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e y \u0440\u0430\u0432\u043d\u043e\u0439 \u0447\u0438\u0441\u043b\u0443 x.<\/p>\n<\/li>\n<li>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 i \u0438 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043e\u0442 0 \u0434\u043e k-1.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i =1, \u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0443\u043c\u043d\u043e\u0436\u0430\u0435\u0442\u0441\u044f \u043d\u0430 y, \u0430 \u0441\u0430\u043c\u043e \u0447\u0438\u0441\u043b\u043e y \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=0, \u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 y \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442.\u00a0<\/p>\n<\/li>\n<\/ol>\n<p>\u0414\u0430\u043d\u043d\u0430\u044f \u0441\u0445\u0435\u043c\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0436\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438 \u0441\u0445\u0435\u043c\u0430 \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e.<\/p>\n<p>\u0412, \u043e\u0431\u0449\u0435\u043c \u0432\u0438\u0434\u0435 \u0441\u0445\u0435\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c<\/p>\n<p>\u0438\u043b\u0438<\/p>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432\u0448\u0438\u0441\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u043e\u0439 \u0441\u0445\u0435\u043c\u044b \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u043c <\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432 Python<\/p>\n<pre><code>def fast_pow(val, p):     s, v,c =1,val,p     while (c!=0):         if (c %2==1):             s = s* v         c = c>>1           v = v*v     return s<\/code><\/pre>\n<h3>\u041b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 \u041c\u043e\u043d\u0442\u0433\u043e\u043c\u0435\u0440\u0438<\/h3>\n<p>\u0414\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0447\u0430\u0441\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0435\u0442 \u0437\u0430\u0449\u0438\u0442\u0443 \u043e\u0442 \u0430\u043a\u0442\u0430\u043a \u043f\u043e \u043f\u043e\u0431\u043e\u0447\u043d\u044b\u043c \u043a\u0430\u043d\u0430\u043b\u0430\u043c \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u043e\u0441\u0442\u0438. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0431\u0438\u0442\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u0432 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 0 \u0438\u043b\u0438 1. \u042d\u0442\u043e \u0434\u0430\u0435\u0442 \u0442\u043e, \u0447\u0442\u043e \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0440\u0430\u0437\u043d\u044b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0438 \u0438\u0437\u0432\u043d\u0435 \u0441\u043b\u043e\u0436\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u044c \u0447\u0442\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442.<\/p>\n<p>\u0414\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0445 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c n \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c.<\/p>\n<ol>\n<li>\n<p>\u0412\u0432\u0435\u0441\u0442\u0438 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 <\/p>\n<\/li>\n<\/ol>\n<ol>\n<li>\n<p>\u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 i \u0438 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043e\u0442 k-1 \u0434\u043e 0.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=0, \u0442\u043e\u0433\u0434\u0430 <\/p>\n<\/li>\n<\/ol>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 m_i=1, \u0442\u043e\u0433\u0434\u0430 <\/p>\n<\/li>\n<\/ol>\n<ol>\n<li>\n<p>\u0412 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 x_1 \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 x \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c n.<\/p>\n<\/li>\n<\/ol>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 (\u043e\u0442 \u0434\u043e log n): \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u0438\u043c\u0435\u044e\u0442 \u043c\u0435\u0441\u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0431\u0438\u0442\u0430.<\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 21 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c 11. \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435.<\/p>\n<ol start=\"6\">\n<li>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 <\/p>\n<\/li>\n<\/ol>\n<pre><code>def powers(val,p):     x1 = 1     x2 = val     bin_k = list(map(int,bin(p)[2:]))         for i in range(len(bin_k)):             if bin_k[i]==0:             x2 = x1*x2             x1 = x1*x1             else:             x1 = x1*x2             x2 = x2*x2        return x1<\/code><\/pre>\n<h3>\u041c\u0435\u0442\u043e\u0434 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435\u0439<\/h3>\n<p>\u0414\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u0432\u0438\u0434\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435\u0439. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0435\u0439 \u0438 \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432 \u043a\u0430\u0436\u0434\u0443\u044e \u0438\u0437 \u043d\u0438\u0445. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0414\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0448\u0438\u0440\u043e\u043a\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0435\u0439 \u0438 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0445, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438. \u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u043b\u044e\u0431\u043e\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u043b\u043e\u0436\u0438\u0442\u044c \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0438 \u0442\u0430\u043a\u043e\u0435 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0435\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440<\/p>\n<p>\u0420\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 \u0432 \u043e\u0431\u0449\u0435\u043c \u0432\u0438\u0434\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0442\u0430\u043a<\/p>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u043b\u043e\u0436\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u043d\u0430 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0434\u0435\u043b\u0435\u0442\u0435\u043b\u0435\u0439. \u0411\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u043e\u0442 2 \u0434\u043e \u043a\u043e\u0440\u043d\u044f \u0438\u0437 n \u0438 \u0435\u0441\u043b\u0438 n \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 \u044d\u0442\u043e\u0442 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u0431\u0443\u0434\u0435\u043c \u043d\u0430 \u043d\u0435\u0433\u043e \u0434\u0435\u043b\u0438\u0442\u044c. \u0418 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437. \u0422\u0430\u043a \u043c\u044b \u0441\u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0431\u0440\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438 \u0438 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u0432 \u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442, \u043a\u043e\u0433\u0434\u0430 n \u0441\u0442\u0430\u043d\u0435\u0442 \u043b\u0438\u0431\u043e 1, \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c.<\/p>\n<pre><code>def factorize(n):     factors = []     i =2     while i*i&lt;=n: # \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c         while n%i==0: # \u043f\u043e\u043a\u0430 n \u043d\u0430 \u043d\u0435\u0433\u043e \u0434\u0435\u043b\u0438\u0442\u0441\u044f         n\/\/=i # \u0434\u0435\u043b\u0438\u043c \u043d\u0430 \u044d\u0442\u043e\u0442 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c         factors.append(i)     i +=1 # \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e n \u0441\u0442\u0430\u043b\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0447\u0438\u0441\u043b\u043e\u043c # \u0438 \u0435\u0433\u043e \u0442\u043e\u0436\u0435 \u043d\u0430\u0434\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435             if n>1:             factors.append(n)     return factors<\/code><\/pre>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/p>\n<pre><code>def power_fact(n,p):     lists = factorize(p)     result = n     for el in lists:         result = result**el<\/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-362412","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/362412","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=362412"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/362412\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=362412"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=362412"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=362412"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}