結果

問題 No.308 素数は通れません
ユーザー te-shte-sh
提出日時 2017-06-27 14:22:12
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,465 bytes
コンパイル時間 987 ms
コンパイル使用メモリ 107,028 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-12 20:31:37
合計ジャッジ時間 3,267 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,944 KB
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 1 ms
6,940 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 1 ms
6,940 KB
testcase_29 AC 1 ms
6,940 KB
testcase_30 AC 1 ms
6,944 KB
testcase_31 AC 1 ms
6,944 KB
testcase_32 AC 1 ms
6,944 KB
testcase_33 AC 1 ms
6,940 KB
testcase_34 AC 1 ms
6,940 KB
testcase_35 AC 1 ms
6,944 KB
testcase_36 AC 1 ms
6,940 KB
testcase_37 AC 1 ms
6,940 KB
testcase_38 AC 1 ms
6,944 KB
testcase_39 AC 1 ms
6,944 KB
testcase_40 AC 1 ms
6,944 KB
testcase_41 AC 1 ms
6,944 KB
testcase_42 AC 1 ms
6,940 KB
testcase_43 AC 1 ms
6,940 KB
testcase_44 AC 1 ms
6,944 KB
testcase_45 AC 1 ms
6,940 KB
testcase_46 AC 1 ms
6,944 KB
testcase_47 AC 1 ms
6,944 KB
testcase_48 AC 1 ms
6,944 KB
testcase_49 AC 1 ms
6,940 KB
testcase_50 AC 1 ms
6,940 KB
testcase_51 AC 1 ms
6,940 KB
testcase_52 AC 1 ms
6,944 KB
testcase_53 AC 1 ms
6,940 KB
testcase_54 AC 1 ms
6,944 KB
testcase_55 AC 1 ms
6,944 KB
testcase_56 AC 1 ms
6,940 KB
testcase_57 AC 1 ms
6,944 KB
testcase_58 AC 1 ms
6,940 KB
testcase_59 AC 0 ms
6,940 KB
testcase_60 AC 1 ms
6,940 KB
testcase_61 AC 1 ms
6,940 KB
testcase_62 AC 0 ms
6,940 KB
testcase_63 AC 1 ms
6,940 KB
testcase_64 AC 1 ms
6,940 KB
testcase_65 AC 2 ms
6,944 KB
testcase_66 AC 1 ms
6,940 KB
testcase_67 AC 1 ms
6,944 KB
testcase_68 AC 0 ms
6,940 KB
testcase_69 AC 2 ms
6,940 KB
testcase_70 AC 1 ms
6,940 KB
testcase_71 AC 1 ms
6,944 KB
testcase_72 AC 1 ms
6,944 KB
testcase_73 AC 2 ms
6,944 KB
testcase_74 AC 1 ms
6,944 KB
testcase_75 AC 1 ms
6,940 KB
testcase_76 AC 1 ms
6,944 KB
testcase_77 AC 1 ms
6,940 KB
testcase_78 AC 2 ms
6,940 KB
testcase_79 AC 1 ms
6,940 KB
testcase_80 AC 1 ms
6,944 KB
testcase_81 AC 1 ms
6,944 KB
testcase_82 AC 1 ms
6,940 KB
testcase_83 AC 1 ms
6,940 KB
testcase_84 AC 1 ms
6,940 KB
testcase_85 AC 1 ms
6,940 KB
testcase_86 AC 1 ms
6,948 KB
testcase_87 AC 2 ms
6,944 KB
testcase_88 AC 1 ms
6,940 KB
testcase_89 AC 1 ms
6,944 KB
testcase_90 AC 1 ms
6,940 KB
testcase_91 AC 2 ms
6,940 KB
testcase_92 AC 2 ms
6,940 KB
testcase_93 AC 2 ms
6,940 KB
testcase_94 AC 1 ms
6,940 KB
testcase_95 AC 1 ms
6,940 KB
testcase_96 AC 1 ms
6,944 KB
testcase_97 AC 1 ms
6,940 KB
testcase_98 AC 1 ms
6,940 KB
testcase_99 AC 1 ms
6,940 KB
testcase_100 AC 1 ms
6,940 KB
testcase_101 AC 1 ms
6,940 KB
testcase_102 AC 1 ms
6,940 KB
testcase_103 AC 1 ms
6,944 KB
testcase_104 AC 1 ms
6,944 KB
testcase_105 AC 1 ms
6,940 KB
testcase_106 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap

void main()
{
  auto s = readln.chomp;
  if (s.length <= 8) {
    auto n = s.to!int;
    if (n < 100)
      calc1(n).writeln;
    else
      calc2(n).writeln;
  } else {
    calc3(s).writeln;
  }
}

const primes100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];

auto calc1(int n)
{
  foreach (w; 3..n) {
    auto q = DList!int(1), v = new bool[](n);
    v[1] = true;

    while (!q.empty) {
      auto p = q.front; q.removeFront();

      int[] c;
      if (p % w > 1 && p-1 > 0) c ~= p-1;
      if (p % w != 0 && p+1 <= n) c ~= p+1;
      if (p-w > 0) c ~= p-w;
      if (p+w <= n) c ~= p+w;

      foreach (ci; c) {
        if (ci == n) return w;
        if (!v[ci] && !primes100.canFind(ci)) {
          v[ci] = true;
          q.insertBack(ci);
        }
      }
    }
  }
  assert(0);
}

auto calc2(int n)
{
  if (n % 8 != 1) return 8;
  n -= 8;

  auto m = n.nsqrt;
  foreach (i; 2..m+1)
    if (n % i == 0) return 8;

  return 14;
}

auto calc3(string s)
{
  auto n = GmpInt(s);

  if ((n % GmpInt(8)).toLong != 1) return 8;
  n -= GmpInt(8);

  if (n.probabPrime(10))
    return 14;
  else
    return 8;
}

pure T nsqrt(T)(T n)
{
  import std.algorithm, std.conv, std.range, core.bitop;
  if (n <= 1) return n;
  T m = 1 << (n.bsr / 2 + 1);
  return iota(1, m).map!"a * a".assumeSorted!"a <= b".lowerBound(n).length.to!T;
}

struct GmpInt
{
  __mpz_struct z;

  this(long v)
  {
    __gmpz_init(&z);
    __gmpz_set_si(&z, v);
  }

  this(string s, int base = 10)
  {
    __gmpz_init(&z);
    __gmpz_set_str(&z, s.toStringz, base);
  }

  auto toLong()
  {
    return __gmpz_get_si(&z);
  }

  auto toString(int base = 10)
  {
    auto sz = __gmpz_sizeinbase(&z, base);
    auto buf = new char[](sz + 2);
    __gmpz_get_str(buf.ptr, base, &z);
    return buf.ptr.fromStringz;
  }

  auto opBinary(string op)(GmpInt v)
    if (op == "+" || op == "-" || op == "*" || op == "%")
  {
    auto r = GmpInt(0);
    static if (op == "+") __gmpz_add(&r.z, &z, &v.z);
    else   if (op == "-") __gmpz_sub(&r.z, &z, &v.z);
    else   if (op == "*") __gmpz_mul(&r.z, &z, &v.z);
    else   if (op == "%") __gmpz_mod(&r.z, &z, &v.z);
    return r;
  }

  auto opOpAssign(string op)(GmpInt v)
    if (op == "+" || op == "-" || op == "*" || op == "%")
  {
    static if (op == "+") __gmpz_add(&z, &z, &v.z);
    else   if (op == "-") __gmpz_sub(&z, &z, &v.z);
    else   if (op == "*") __gmpz_mul(&z, &z, &v.z);
    else   if (op == "%") __gmpz_mod(&z, &z, &v.z);
    return this;
  }

  int probabPrime(int reps)
  {
    return __gmpz_probab_prime_p(&z, reps);
  }
}

extern(C) pragma(inline, false)
{
  alias __mp_limb_t = ulong;

  struct __mpz_struct
  {
    int _mp_alloc;
    int _mp_size;
    __mp_limb_t* _mp_d;
  }

  alias mpz_srcptr = const(__mpz_struct)*;
  alias mpz_ptr = __mpz_struct*;

  void __gmpz_init(mpz_ptr);

  void __gmpz_set_si(mpz_ptr, long);
  int __gmpz_set_str(mpz_ptr, const char*, int);

  void __gmpz_add(mpz_ptr, mpz_srcptr, mpz_srcptr);
  void __gmpz_sub(mpz_ptr, mpz_srcptr, mpz_srcptr);
  void __gmpz_mul(mpz_ptr, mpz_srcptr, mpz_srcptr);
  void __gmpz_mod(mpz_ptr, mpz_srcptr, mpz_srcptr);

  int __gmpz_probab_prime_p(mpz_ptr, int reps);

  size_t __gmpz_sizeinbase(mpz_srcptr, int);
  char *__gmpz_get_str(char*, int, mpz_srcptr);
  long __gmpz_get_si(mpz_srcptr);
}

pragma(lib, "gmp");
0