結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー yuppe19 😺
提出日時 2017-10-17 10:11:54
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 2,245 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,473 ms
コンパイル使用メモリ 169,200 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:14:29
合計ジャッジ時間 2,478 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:95:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |   int Q; scanf("%d", &Q);
      |          ~~~~~^~~~~~~~~~
main.cpp:97:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |     u64 n; scanf("%llu", &n);
      |            ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
using u64 = unsigned long long;

u64 uz = time(NULL);
u64 xorshift64() {
  uz ^= uz << 13;
  uz ^= uz >> 7;
  uz ^= uz << 17;
  return uz;
}

// floor( log2(x) )
int log2_64(u64 x) {
  if(x == 0) { return 0; }
  return 63 - __builtin_clzll(x);
}

// 戻り値が 0 ならオーバーフローなどで失敗したことを表すことにする
u64 mypow(u64 a, int b) {
  if(log2_64(a) * b > 64) { return 0; }
  u64 res = 1ULL;
  while(b) {
    if(b & 1) { res *= a; }
    a *= a;
    b >>= 1;
  }
  return res;
}

u64 mod_mul(u64 a, u64 b, u64 m) {
  __uint128_t a128 = a;
  a128 *= b;
  a128 %= m;
  return a128;
}

u64 mod_pow(u64 x, u64 k, u64 m) {
  if(k == 0) { return 1; }
  if(k & 1) { return mod_mul(x, mod_pow(x, k-1, m), m); }
  return mod_pow(mod_mul(x, x, m), k>>1, m);
}

bool is_probable_prime(u64 n) {
  constexpr int k = 30;
  if(n < 2) { return false; }
  for(u64&& p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}) {
    if(n < p * p)  { return true; }
    if(n % p == 0) { return false; }
  }
  u64 s = 0,
      d = n-1;
  while(!(d & 1)) { ++s, d>>=1; }
  for(int loop=0; loop<k; ++loop) {
    u64 a = xorshift64() % (n-3) + 2,
        x = mod_pow(a, d, n);
    if(x == 1 || x == n-1) { continue; }
    bool flag = false;
    for(u64 loop2=1; loop2<s; ++loop2) {
      x = mod_mul(x, x, n);
      if(x == n-1) { flag = true; break; }
    }
    if(!flag) { return false; }
  }
  return true;
}

u64 g(u64 pa, int a) {
  u64 lo = 0, hi = u64(powl(pa, 1.L/a)) + 2;
  while(hi - lo > 1) {
    u64 md = (lo + hi) / 2;
    u64 pw = mypow(md, a);
    if(pw == 0 || pw > pa) { hi = md; }
    else { lo = md; }
  }
  return lo;
}

bool f(u64 n) {
  if(n == 2) { return false; }
  if(n % 2 == 0) { return true; }
  for(u64 b=2; b<n; b*=2) {
    u64 pa = n - b;
    for(u64 a=1, mul=3; mul<=pa; ++a, mul*=3) {
      u64 p = g(pa, a);
      if(mypow(p, a) == pa && is_probable_prime(p)) { return true; }
    }
  }
  return false;
}

int main(void) {
  int Q; scanf("%d", &Q);
  for(int loop=0; loop<Q; ++loop) {
    u64 n; scanf("%llu", &n);
    assert(1 <= n && n <= u64(powl(10, 18)));
    bool able = f(n);
    puts(able ? "Yes" : "No");
  }
  return 0;
}
0