#184234 (D) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	te-sh
提出日時	2017-06-27 14:22:12
言語	D (dmd 2.106.1)
結果	AC
実行時間	6 ms / 1,000 ms
コード長	3,465 bytes
コンパイル時間	952 ms
コンパイル使用メモリ	93,212 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-03 14:48:06
合計ジャッジ時間	4,297 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,384 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	1 ms 4,380 KB
testcase_15	AC	1 ms 4,380 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	2 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	2 ms 4,380 KB
testcase_24	AC	1 ms 4,380 KB
testcase_25	AC	2 ms 4,380 KB
testcase_26	AC	1 ms 4,376 KB
testcase_27	AC	2 ms 4,376 KB
testcase_28	AC	2 ms 4,376 KB
testcase_29	AC	2 ms 4,380 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	2 ms 4,376 KB
testcase_32	AC	1 ms 4,376 KB
testcase_33	AC	1 ms 4,380 KB
testcase_34	AC	2 ms 4,376 KB
testcase_35	AC	1 ms 4,380 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,376 KB
testcase_38	AC	1 ms 4,376 KB
testcase_39	AC	2 ms 4,376 KB
testcase_40	AC	1 ms 4,380 KB
testcase_41	AC	2 ms 4,376 KB
testcase_42	AC	2 ms 4,380 KB
testcase_43	AC	2 ms 4,380 KB
testcase_44	AC	1 ms 4,376 KB
testcase_45	AC	1 ms 4,380 KB
testcase_46	AC	1 ms 4,380 KB
testcase_47	AC	1 ms 4,376 KB
testcase_48	AC	2 ms 4,376 KB
testcase_49	AC	2 ms 4,380 KB
testcase_50	AC	2 ms 4,380 KB
testcase_51	AC	2 ms 4,380 KB
testcase_52	AC	2 ms 4,380 KB
testcase_53	AC	2 ms 4,376 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	2 ms 4,376 KB
testcase_56	AC	2 ms 4,376 KB
testcase_57	AC	1 ms 4,376 KB
testcase_58	AC	1 ms 4,376 KB
testcase_59	AC	2 ms 4,376 KB
testcase_60	AC	6 ms 4,376 KB
testcase_61	AC	2 ms 4,376 KB
testcase_62	AC	2 ms 4,376 KB
testcase_63	AC	1 ms 4,380 KB
testcase_64	AC	1 ms 4,376 KB
testcase_65	AC	1 ms 4,380 KB
testcase_66	AC	2 ms 4,376 KB
testcase_67	AC	2 ms 4,376 KB
testcase_68	AC	2 ms 4,380 KB
testcase_69	AC	2 ms 4,376 KB
testcase_70	AC	2 ms 4,376 KB
testcase_71	AC	2 ms 4,380 KB
testcase_72	AC	1 ms 4,376 KB
testcase_73	AC	2 ms 4,376 KB
testcase_74	AC	1 ms 4,376 KB
testcase_75	AC	1 ms 4,376 KB
testcase_76	AC	1 ms 4,376 KB
testcase_77	AC	1 ms 4,376 KB
testcase_78	AC	1 ms 4,376 KB
testcase_79	AC	2 ms 4,376 KB
testcase_80	AC	2 ms 4,380 KB
testcase_81	AC	1 ms 4,376 KB
testcase_82	AC	1 ms 4,380 KB
testcase_83	AC	1 ms 4,376 KB
testcase_84	AC	1 ms 4,376 KB
testcase_85	AC	2 ms 4,376 KB
testcase_86	AC	1 ms 4,376 KB
testcase_87	AC	2 ms 4,376 KB
testcase_88	AC	1 ms 4,380 KB
testcase_89	AC	2 ms 4,376 KB
testcase_90	AC	2 ms 4,380 KB
testcase_91	AC	2 ms 4,380 KB
testcase_92	AC	2 ms 4,376 KB
testcase_93	AC	2 ms 4,384 KB
testcase_94	AC	1 ms 4,376 KB
testcase_95	AC	2 ms 4,376 KB
testcase_96	AC	1 ms 4,376 KB
testcase_97	AC	2 ms 4,380 KB
testcase_98	AC	1 ms 4,376 KB
testcase_99	AC	1 ms 4,380 KB
testcase_100	AC	1 ms 4,380 KB
testcase_101	AC	2 ms 4,380 KB
testcase_102	AC	1 ms 4,376 KB
testcase_103	AC	2 ms 4,376 KB
testcase_104	AC	1 ms 4,376 KB
testcase_105	AC	2 ms 4,376 KB
testcase_106	AC	1 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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");

yukicoder

結果

テストケース

ソースコード