求N的N次方（快速幂取模）

2019-04-14 21:04发布

站内文章 / 模拟电子
9719 0 921

分治算法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

例题：给定一个整数N（N<=1 000 000 000),求N的N次方的最后一个数字。 首先，暴力的时间复杂度为O（N），对于较大的N显然太慢。所以我们选取快速幂取模 的方法，基于公式： （a×b）%c=（（a%c)×（b%c））%c。时间复杂度为log2 N； #include using namespace std; long long mod(long long a,long long b) { if(b==1) return a; long long s=mod(a,b/2)%10;//将问题分成两个部分 if(b%2==0) return (s*s)%10; else return (s*s*a)%10; } int main() { int n; cin>>n; cout<  

热门文章