結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー LanatusLanatus
提出日時 2022-12-12 22:28:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,034 bytes
コンパイル時間 2,126 ms
コンパイル使用メモリ 197,320 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-24 12:14:07
合計ジャッジ時間 3,009 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define all(v) begin(v), end(v)

using namespace std;

const int MOD = 1e9 + 7;

long long modpow(long long a, long long n, long long m = MOD) {
  if (n <= 0) return 1LL;
  if (n % 2LL) return a * modpow(a, n-1, m) % m;
  long long t = modpow(a, n/2, m);
  return t % m * t % m;
}


bool isPrime(long long n) {
  if (n == 2) return true;
  if (n == 1 || n % 2 == 0) return false;

  long long m = n - 1;
  long long s = 0;

  while (m % (1LL << s) == 0) ++s;

  long long d = m / (1LL << s);

  vector<long long> testNumbers {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

  for (auto a : testNumbers) {
    if (a == n) continue;
    
    long long x = modpow(a, d, n);
    int r = 0;

    if (x == 1) continue;

    while (x != m) {
      x = modpow(x, 2, n);
      ++r;

      if (x == 1 || r == s) return false;
    }
  }

  return true;
}


signed main() {
  int n;
  cin >> n;

  for (int i = 0; i < n; ++i) {
    long long x;
    cin >> x;

    cout << x << " " << isPrime(x) << endl;
  }

  return 0;
}
0