結果

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

コンパイルメッセージ
main.cpp: In function ‘u64 g(u64, int)’:
main.cpp:71:24: error: ‘powl’ was not declared in this scope
   71 |   u64 lo = 0, hi = u64(powl(pa, 1.L/a)) + 2;
      |                        ^~~~
In file included from /usr/include/c++/11/cassert:44,
                 from main.cpp:3:
main.cpp: In function ‘int main()’:
main.cpp:98:31: error: ‘powl’ was not declared in this scope
   98 |     assert(1 <= n && n <= u64(powl(10, 18)));
      |                               ^~~~
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 # 

#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