模重复平方计数法的C++实现

2019-04-13 21:06发布

站内文章 / 模拟电子
10522 0 1438
/* * @author Novicer * language : C++/C */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const double eps(1e-8); typedef long long lint; lint b,n,m; int main(){ cout << "模重复平方计数法" << endl; cout << "Author : Novicer and you" << endl; cout << "ver : 0.1" << endl; while(1){ cout << "输入 b^n(mod m) 中b , n , m值，空格分割，回车结束" << endl; cin >> b >> n >> m; lint b_begin = b; lint n_begin = n; lint i = 0; lint a = 1; int n_2 ; cout << "计算过程如下：（式中“==”符号即恒等符号）" << endl; cout << "a = " << a << ", b = b0 = " << b << endl; if(n == 0) printf("ans = 1 "); while(n){ if(n & 1){ a = (a * b) % m; n_2 = 1; } else{ n_2 = 0; } b = (b * b) % m; n >>= 1; cout << "n" << i << " = " << n_2 << ", "; cout << "a" << i << " == " << a << ", "; cout << "b" << i + 1 << " == " << "b" << i << "^2" << " == " << b << "(mod " << m << ")" << endl; i++; } cout << "ans = " << a << endl; printf("即: %lld^%lld == %lld(mod %lld) ",b_begin,n_begin,a,m); } return 0; }

热门文章