結果

問題 No.371 ぼく悪いプライムじゃないよ
ユーザー te-shte-sh
提出日時 2017-07-20 14:15:41
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 1,351 bytes
コンパイル時間 1,023 ms
コンパイル使用メモリ 116,648 KB
実行使用メモリ 8,752 KB
最終ジャッジ日時 2023-09-03 15:19:10
合計ジャッジ時間 4,550 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,264 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 4 ms
4,380 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 TLE -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.typecons;  // Tuple, Nullable, BigFlags

void main()
{
  auto rd = readln.split.to!(long[]), l = rd[0], h = rd[1];

  auto p = primes(h.nsqrt.to!int);

  long calc(long n, int q)
  {
    auto r = n/q - 1;

    foreach (pi; p) {
      if (pi >= q || pi * pi > n/q) break;
      r -= calc(n/q, pi);
    }

    return r;
  }

  foreach_reverse (pi; p) {
    auto r1 = calc(h, pi);
    auto r2 = calc(l-1, pi);
    if (r1 - r2 > 0) {
      auto s = iota(l, h+1)
        .map!((a) => Tuple!(long, long)(a, calc(a, pi)))
        .assumeSorted!"a[1] < b[1]"
        .upperBound(Tuple!(long, long)(0, r1-1));
      writeln(s.front[0]);
      return;
    }
  }
}

pure T[] primes(T)(T n)
{
  import std.algorithm, std.bitmanip, std.conv, std.range;

  auto sieve = BitArray();
  sieve.length((n + 1) / 2);
  sieve = ~sieve;

  foreach (p; 1..((nsqrt(n) - 1) / 2 + 1))
    if (sieve[p])
      for (auto q = p * 3 + 1; q < (n + 1) / 2; q += p * 2 + 1)
        sieve[q] = false;

  auto r = sieve.bitsSet.map!(to!T).map!("a * 2 + 1").array;
  r[0] = 2;

  return r;
}

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;
}
0