結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー yuppe19 😺
提出日時 2017-10-15 22:37:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,996 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 52,492 KB
最終ジャッジ日時 2024-11-14 20:15:16
合計ジャッジ時間 793 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘u64 g(u64, int)’:
main.cpp:67:20: error: ‘powl’ was not declared in this scope
   67 |   u64 lo = 1, hi = powl(pa, f80(1)/a) + 1;
      |                    ^~~~
main.cpp: In function ‘int main()’:
main.cpp:90:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   90 |   int Q; scanf("%d", &Q);
      |          ~~~~~^~~~~~~~~~
main.cpp:92:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |     u64 n; scanf("%llu", &n);
      |            ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

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

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

u64 mypow(u64 a, u64 b) {
  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) {
  u64 res = 0;
  a %= m;
  while(b) {
    if(b & 1) { (res += a) %= m; }
    (a <<= 1) %= m;
    b >>= 1;
  }
  return res;
}

u64 mod_pow(u64 x, u64 k, u64 m) {
  if(k == 0) { return 1; }
  if(!(k & 1)) { return mod_pow(mod_mul(x, x, m), k>>1, m); }
  return mod_mul(x, mod_pow(x, k-1, m), 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 = 1, hi = powl(pa, f80(1)/a) + 1;
  while(hi - lo > 1) {
    u64 md = (lo + hi) / 2;
    if(mypow(md, a) <= pa) { lo = md; }
    else { hi = 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);
    bool able = f(n);
    puts(able ? "Yes" : "No");
  }
  return 0;
}
0