読者です 読者をやめる 読者になる 読者になる

繰り返し二乗法(2題)

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
この本(通称:蟻本)の章末で紹介されている練習問題をひたすらといている。

繰り返し二乗法。べき乗の高速な計算アルゴリズムなんだけど、こういうのって組み込み関数みたいにモジュール化してしまえば、あとは使い回せばいいだけだよね。問題ごとに何回も同じ関数を実装するのは労力の無駄。Don't repeat yourself の精神が大事だと思う。

POJ3641: Pseudoprime Numbers

3641 -- 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;
    }
  }
}

問題概要

与えられた整数の組を使ってべき乗の和の剰余を求める問題。

解法

繰り返し二乗法でがんばる。が、関数はコピペで済むので、がんばるところがない。

#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;
  }
}