#215376 (C++17) No.577 Prime Powerful Numbers

• 問題: No.577 Prime Powerful Numbers
• ユーザー: Ryuhei Mori
• 提出日時: 2017-11-10 17:51:52
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 23 ms / 2,000 ms
• コード長: 6,099 bytes
• コンパイル時間: 1,082 ms
• コンパイル使用メモリ: 81,848 KB
• 最終ジャッジ日時: 2025-01-05 03:55:01
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 10

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:279:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  279 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
main.cpp:282:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  282 |     scanf("%ld", &n);
      |     ~~~~~^~~~~~~~~~~

ソースコード

#include <cstdio>
#include <cstdint>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

typedef __int128 int128_t;
typedef unsigned __int128 uint128_t;


static inline uint32_t modpow32(uint32_t a, uint32_t k, uint32_t n){
  uint32_t r;
  for(r=1;k;k/=2){
    if(k&1) r = (uint64_t)r*a%n;
    a = (uint64_t) a*a%n;
  }
  return r;
}

int is_prime32(uint32_t n){
  static const uint32_t as32[] = {2, 7, 61};
  int i, j;
  int r = __builtin_ctz(n-1);
  uint32_t d = (n-1) >> r;
  for(i=0;i<3;i++){
    uint32_t a = as32[i] % n;
    if(a == 0) return 1;
    uint32_t t = modpow32(a, d, n);
    if(t == 1) continue;
    for(j=0;t!=n-1;j++){
      if(j == r-1) return 0;
      t = (uint64_t) t * t % n;
      if(t == 1) return 0;
    }
  }
  return 1;
}


static inline uint64_t ex_gcd(uint64_t y){
  int i;
  uint64_t u, v;
  u = 1; v = 0;
  uint64_t x = 1LL<<63;

  for(i=0;i<64;i++){
    if(u&1){
      u = (u + y) / 2;
      v = v/2 + x;
    }
    else {
      u >>= 1; v >>= 1;
    }
  }

  return -v;
} 


static inline uint64_t MR(uint128_t x, uint64_t m, uint64_t n){
  int64_t z = (x >> 64) - ((((uint64_t) x * m) * (uint128_t) n) >> 64);
  return z < 0 ? z + n : z;
}

static inline uint64_t RM(uint64_t x, uint64_t r2, uint64_t m, uint64_t n){
  return MR((uint128_t) r2 * x, m, n);
}

static inline uint64_t mulmod64(uint64_t x, uint64_t y, uint64_t m, uint64_t n){
  return MR((uint128_t) x*y, m, n);
}


int jacobi(int64_t a, uint64_t n){
  uint64_t t;
  int j = 1;
  while(a){
    if(a<0){
      a = -a;
      if((n&3)==3) j = -j;
    }
    int ba = __builtin_ctzll(a);
    a >>= ba;
    if(((n&7)==3||(n&7)==5) && (ba&1)) j = -j;
    if((a&n&3)==3) j = -j;
    t = a; a = n; n = t;
    a %= n;
    if(a>n/2) a-=n;
  }
  return n == 1 ? j : 0;
}


static inline uint64_t addmod64(uint64_t x, uint64_t y, uint64_t n){
  return x + y >= n ? x + y - n : x + y;
}

static inline uint64_t submod64(uint64_t x, uint64_t y, uint64_t n){
  return x >= y  ? x - y : x - y + n;
}


uint64_t bgcd(uint64_t x, uint64_t y){
  int bx = __builtin_ctzll(x);
  int by = __builtin_ctzll(y);
  int k = (bx < by) ? bx : by;
  x >>= bx;
  y >>= by;
  while(x!=y){
    if(x < y){
      y -= x;
      y >>= __builtin_ctzll(y);
    }
    else {
      x -= y;
      x >>= __builtin_ctzll(x);
    }
  }
  return x << k;
}


int is_prime64(const uint64_t n){
  const uint64_t one = -1ULL % n + 1;
  const uint64_t r2 = (uint128_t) (int128_t) -1 % n + 1;
  const uint64_t m = ex_gcd(n);

  {
    uint64_t d = (n-1) << __builtin_clzll(n-1);
    uint64_t t = one << 1;
    if(t >= n) t -= n;
    for(d<<=1;d;d<<=1){
      t = mulmod64(t, t, m, n);
      if(d>>63){
        t <<= 1;
        if(t>=n) t -= n;
      }
    }
    if(t != one){
      uint64_t x = (n-1) & -(n-1);
      uint64_t mone = n - one;
      for(x>>=2;t!=mone;x>>=1){
        if(x == 0) return 0;
        t = mulmod64(t, t, m, n);
  //      if(t == one) return 0;
      }
    }
  }


  {
    int64_t D = 5;
    int i;
    for(i=0;jacobi(D, n) != -1 && i<64;i++){
      if(i==32){
        uint32_t k = round(sqrtl(n));
        if(k*k == n) return 0;
      }
      if(i&1) D -= 2;
      else D += 2;
      D = -D;
    }
//    if(i==64) puts("ERROR");

    uint64_t Q = RM(D < 0 ? (1-D)/4%n : n - (D-1)/4%n, r2, m, n);

    uint64_t u, v, Qn;
    uint64_t k = (n+1) << __builtin_clzll(n+1);
    u = one; v = one;
    Qn = Q;
    D %= (int64_t) n;
    D = RM(D < 0 ? n+D : D, r2, m, n);
    for(k<<=1;k;k<<=1){
      u = mulmod64(u,v,m,n);
      v = submod64(mulmod64(v,v,m,n), addmod64(Qn, Qn, n), n);
      Qn = mulmod64(Qn, Qn, m, n);
      if(k>>63){
        uint64_t uu = addmod64(u, v, n);
        if(uu&1) uu += n;
        uu >>= 1;
        v = addmod64(mulmod64(D,u,m,n), v, n);
        if(v&1) v += n;
        v >>= 1;
        u = uu;
        Qn = mulmod64(Qn, Q, m, n);
      }
    }

    if(u == 0 || v == 0) return 1;
    uint64_t x = (n+1) & ~n;
    for(x>>=2;x;x>>=1){
      u = mulmod64(u,v,m,n);
      v = submod64(mulmod64(v,v,m,n), addmod64(Qn, Qn, n), n);
      if(v == 0) return 1;
      Qn = mulmod64(Qn, Qn, m, n);
    }
  }

  return 0;
}

int is_prime(uint64_t n){
  uint64_t g;
  if(n <= 1) return 0;
  if(n <= 3) return 1;
  if(!(n & 1)) return 0;
  g = bgcd(n, 307444891294245705ULL);
  if(g == n) return n == 5 || n == 7 || n == 11 || n == 13 || n == 17 || n == 19 || n == 23 || n == 29 || n == 31 || n == 37 || n == 41 || n == 43 || n == 47;
  if(g != 1) return 0;
  if(n < (1ULL << 32)) return is_prime32(n);
  return is_prime64(n);
}



uint32_t is_square(uint64_t n){
  if((0xfffdffeffdfefdecULL >> (n & 0x3F)) & 1) return 0;
  uint32_t k = round(sqrt(n));
  if(k * k == n) return k;
  else return 0;
}

uint32_t is_cubic(uint64_t n){
  if((0xfffffffff7fffefcULL >> (n & 0x3F)) & 1) return 0;
  uint32_t k = round(cbrt(n));
  if(k * k * k == n) return k;
  else return 0;
}

std::vector<uint64_t> vec_pp;

const int maxp = 7130;
//const int maxp = 1<<16;
//const int maxp = 2642246;
int sieve_p[maxp/2];

void make_set_pp(){
  std::set<uint64_t> set_pp;
  uint32_t i;
  for(i=3;i<maxp;i+=2){
    if(!sieve_p[i/2]){
      uint64_t j;
      for(j=3*i;j<maxp;j+=2*i){
        sieve_p[j/2] = 1;
      }
      j=i;
      do { set_pp.insert(j);} while(!__builtin_umulll_overflow(j, i, (long long unsigned *)&j));
     }
  }
  vec_pp = std::vector<uint64_t>(set_pp.begin(), set_pp.end());
}




int is_oddprimepower64(uint64_t n){
  if(n == 1) return 0;
  if(std::binary_search(vec_pp.begin(), vec_pp.end(), n)) return 1;
  uint32_t k = is_square(n);
  if(k){
    n = k;
    k = is_square(n);
    if(k) return is_prime(k);
    else return is_prime(n);
  }
  k = is_cubic(n);
  if(k) return is_prime(k);

  return is_prime(n);
}


int main(){
  int i, q;

  make_set_pp();

  scanf("%d", &q);
  for(i=0;i<q;i++){
    uint64_t n;
    scanf("%ld", &n);
    if(n<=2) puts("No");
    else if((n&1)==0) puts("Yes");
    else {
      uint64_t j;
      for(j=2; j<n; j<<=1){
        if(is_oddprimepower64(n-j)){
          break;
        }
      }
      if(j>=n) puts("No"); else puts("Yes");
    }
  }
  return 0;
}