Loading... ##二分 <font color=#008000>~~没为啥就是想写了~~</font> **模板** ```cpp int l=beign,r=end; while(l<r)/*while(r-l<eps)*/{ int mid=(l+r)>>1; if(check(mid)){ l=mid+1;//r=mid-1; } else{ r=mid-1;//l=mid-1; } } ans=l; ``` ####用处: 1.在某情况成立的情况下,其规模更大或其规模更小的情况也成立,就可以用二分法求ans 2.与其他算法结合,并非检查的函数check,而是e.g.：A-B problemの排序去重二分查找=。= ####时间复杂度 $O(log_2n)$ ####应用 1.快速幂和快速乘 ```cpp template<class T> long long quick_pow(T a,T b,T c){ int res=1;//attention! while(b){ if(b&1)res=res*a%c; a*=a%c; b>>=1; } return res; } template<class T> long long quick_mul(T a,T b,T c){ int res=0;//attention! while(b){ if(b&1)res=(res+a)%c a=(a+a)%c; b>>=1; } return res; } ``` 最后修改：2021 年 05 月 23 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用，请随意赞赏
