結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー Lanatus
提出日時 2022-12-12 22:18:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,034 bytes
コンパイル時間 1,810 ms
コンパイル使用メモリ 194,384 KB
最終ジャッジ日時 2025-02-09 10:36:44
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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) % MOD;
  long long t = modpow(a, n/2);
  return t % MOD * t % MOD;
}


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