Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"OOOVOOO","updateTime":1563404259000,"title":"ex_tjy 慢速幂(极不正经版)","dislikeCnt":15,"content":"update:为了体现本文的不正经,作者自己踩一脚\n本文将为大家伙介绍由**tjy**大神提出并由ooo蒟蒻证明的慢速幂\n如不是闲得慌,本着珍爱生命的原则,\n建议:\u003ch2\u003e请勿浏览\u003c/h2\u003e\n\n----\n\n-----\n\n并不华丽的分界线\n\n----\n\n-----\n\u003ch1\u003e正文\u003c/h1\u003e\n\n----\n\u003ch2\u003e引子:\u003c/h2\u003e\nOVO\n\t\t\t听说过二分吗,少年?\n\t\t\t听说过快速幂吗,少年?\n\t\t\t那么,如果把他们结合起来,又会发生什么呢?\n\t\t\t答案是:慢速幂;\n\t\t\t支持\u003ccode\u003eunsigned long long\u003c/code\u003e范围内O(64)计算\n\u003ch2\u003e机理:\u003c/h2\u003e\nOVO\n对答案区间进行二分\n定义\u003ccode\u003eminn\u003d1,maxn\u003dinf(极大值)\u003c/code\u003e\n我们可以考虑:\n1. 对于a^b\u003da^b,可推得:log a a^b\u003db;\n2. 由换底公式得:lg a^b/lg a\u003db;\n3. 由等式的基本性质得:lg a^b\u003db * lg a;\n于是乎,我们会开心的发现,我们已经可以通过二分枚举a^b求解了\n完结撒~~\n\n----\n撒什么花\n我们还没解释为什么它是慢速幂呢好吧!!!\n因为毕竟是二分,复杂度为O(log 2 n);\n有因为n被我们严格限制为2^64;\n故时间复杂度恒为\u003ci class\u003d\"fa fa-spin\"\u003eO(64)\u003c/i\u003e\n故亦被miemeng称为\"恒速幂\";\n易证:对于任意 n!\u003d1且n属于N* ,n^64\u003e\u003d2^64;\n所以暴力连乘时间复杂度O(n\u003c\u003d64)\n我们可爱的二分慢速幂效率等于连乘当且仅当\u003ccode\u003ea\u003d\u003d2,b\u003d\u003d64\u003c/code\u003e\n故称慢速幂;\n至于应用?\n装*?\n或许也只有这一点用处了.........................\n那为什么还会打这么多字来介绍这毫无用处的东西(懵.png)\n\n-----\n\u003cdel\u003e\n要知道我们要有探索精神,\n既然这种想法被提出了\n我们至少也要证明它是无用的\n否则还不如不要提出来(毫无征兆的的大段鸡汤)\u003c/del\u003e\n..................................\n所以,完结撒花!\n(不要因为我浪费了大家的生命打我~)","threadId":49794,"likeCnt":10,"createTime":1563197689000,"isWorkbook":false,"viewCnt":2111,"openness":2,"fav":false,"id":1288,"trustable":false}