繰り返し二乗法（2題）
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本（通称：蟻本）の章末で紹介されている練習問題をひたすらといている。
繰り返し二乗法。べき乗の高速な計算アルゴリズムなんだけど、こういうのって組み込み関数みたいにモジュール化してしまえば、あとは使い回せばいいだけだよね。問題ごとに何回も同じ関数を実装するのは労力の無駄。Don't repeat yourself の精神が大事だと思う。
POJ3641: Pseudoprime Numbers
解法
まあ、繰り返し二乗法だ。「擬素数は素数でない」という定義らしいので、p が素数かどうかもチェックしておく。素数のチェックはミラー・ラビン法で。べき剰余とか素数判定の関数はスパゲッティソースからお借りした。
#include <fstream> #include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; //------- 大きな数の (a * b) % m ----------- long long modMult(long long a, long long b, long long m) { long long res = 0; long long exp = a % m; while (b) { if (b & 1) { res += exp; if (res > m) res -= m; } exp <<= 1; if (exp > m) exp -= m; b >>= 1; } return res; } //-------- べき剰余 (a ^ b) % m -------------------- long long powMod(long long a, long long b, long long m) { long long res = 1; long long exp = a % m; while (b) { if (b & 1) res = modMult(res, exp, m); exp = modMult(exp, exp, m); b >>= 1; } return res; } //-------- Miilar-Robin Test による素数判定 ----------- bool suspect(long long a, int s, long long d, long long n) { long long x = powMod(a, d, n); if (x == 1) return true; for (int r = 0; r < s; ++r) { if (x == n - 1) return true; x = modMult(x, x, n); } return false; } // {2,7,61,-1} is for n < 4759123141 (= 2^32) // {2,3,5,7,11,13,17,19,23,-1} is for n < 10^16 (at least) bool isPrime(long long n) { if (n <= 1 || (n > 2 && n % 2 == 0)) return false; int test[] = {2,3,5,7,11,13,17,19,23,-1}; long long d = n - 1, s = 0; while (d % 2 == 0) ++s, d /= 2; for (int i = 0; test[i] < n && test[i] != -1; ++i) if (!suspect(test[i], s, d, n)) return false; return true; } int main() { #ifndef ONLINE_JUDGE ifstream cin("../test.txt"); #endif long long p, a; while (true) { cin >> p >> a; if (!(p | a)) break; long long a_p = powMod(a, p, p); if (a_p == a && !isPrime(p)) { cout << "yes" << endl; } else { cout << "no" << endl; } } }
POJ1995:
問題概要
与えられた整数の組を使ってべき乗の和の剰余を求める問題。
解法
繰り返し二乗法でがんばる。が、関数はコピペで済むので、がんばるところがない。
#include <fstream> #include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; //------- 大きな数の (a * b) % m ----------- long long modMult(long long a, long long b, long long m) { long long res = 0; long long exp = a % m; while (b) { if (b & 1) { res += exp; if (res > m) res -= m; } exp <<= 1; if (exp > m) exp -= m; b >>= 1; } return res; } //-------- べき剰余 (a ^ b) % m -------------------- long long powMod(long long a, long long b, long long m) { long long res = 1; long long exp = a % m; while (b) { if (b & 1) res = modMult(res, exp, m); exp = modMult(exp, exp, m); b >>= 1; } return res; } int main() { #ifndef ONLINE_JUDGE ifstream cin("../test.txt"); #endif // 入力 int z; cin >> z; while (z--) { long long m; int h; cin >> m >> h; vector<long long> a(h); vector<long long> b(h); for (int i = 0; i < h; i++) { cin >> a[i] >> b[i]; } // 計算 long long sum = 0; for (int i = 0; i < h; i++) { sum += powMod(a[i], b[i], m); sum %= m; } cout << sum << endl; } }
