結果

問題 No.2795 Perfect Number
コンテスト
ユーザー tobbie
提出日時 2024-06-30 17:39:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,366 bytes
コンパイル時間 1,644 ms
コンパイル使用メモリ 170,720 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-30 17:39:14
合計ジャッジ時間 2,787 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
using ll = long long int;

int mod_pow(int x, int n, int mod) {
  int ret = 1;
  while (n > 0) {
    if ((n & 0x01) != 0)
      ret = (long long)ret * x % mod;
    x = (long long)x * x % mod;
    n >>= 1;
  }
  return ret;
}

bool miller_rabin(ll n) {      // is prime
  if (n == 2)
    return true;
  if (n == 1 || n % 2 == 0)
    return false;
  ll s = 0;
  while (((n-1) & -(n-1)) > (1 << s))
    s++;
  int d = (n-1) / ((n-1) & -(n-1));         // n-1 = 2^s*d
  vector<int> tests = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  // n - 1 = a^s * d
  for (int a : tests) {
    if (a == n)
      continue;
    ll x = mod_pow(a, d, n);   // x = a^d(mod n)
    if (x == 1)
      continue;
    int r = 0;
    while (x != n-1) {          // r = 0 -> s
      x = mod_pow(x, 2, n);     // x = (a^d)^2(mod n) = a^(2^(rd))(mod n)
      r++;
      if (x == 1 || r == s)     // x^2 = 1(mod n) -> not prime number
	return false;
    }
  }
  return true;
}

int main() {
  ll N;
  cin >> N;
  vector<int> tests = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  for (int n : tests) {
    ll p = pow(2, n) - 1;
    if (miller_rabin(p)) {
      ll q = pow(2, n-1) * p;
      if (N == q) {
	cout << "Yes" << endl;
	return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}
0