模的指数运算

• 真言

家人万岁，亲情万岁。

• 引言

哎呀，放假了，回家了，村里建设挺好哈，晚上大娘婶婶出来跳舞了，我还在coding，有鸡叫的日子真好，喜欢农村，I‘m a 农民，还不是村干部！

• 模的指数运算

原来模的功能是这么的强大，以前没有太在意它，实在是愧疚呀。模赋予了单位很大的意义，使得大数据可以被我们处理，这就是我对模的理解。 问题定义：给定x和y，计算x的y次方模N的值，其中N有数百位长。 算法如下（递归的算法）
原理如下

• 实验

• 代码
  • 只要算法是递归的，我都会在转换成非递归的算法，同时给大家。
  • test1.cpp
  • #include #include using namespace std; // function modexp in recursion int modexp_re(int x,int y,int N); // function modexp without recursion int modexp_nonre(int x,int y,int N); int const N = 10000 ; // function main int main() { int a,b,i = 0; while(i < 100) { a = rand()%10000; b = rand()%10000; cout<<"a="< * s = new stack; while(y >= 1) { s->push(y); y = y/2; } result = x % N; while(s->size()>1) { z = s->top(); s->pop(); result = ( (result%N) * (result%N) )%N; if(s->empty()) break; else if(z*2 != s->top()) { result = (result * (x%N) )%N; } } return result; } }