結果

問題 No.371 ぼく悪いプライムじゃないよ
コンテスト
ユーザー te-sh
提出日時 2017-07-20 14:15:41
言語 D
(dmd 2.111.0)
結果
WA  
実行時間 -
コード長 1,351 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 982 ms
コンパイル使用メモリ 122,524 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-06-12 21:02:19
合計ジャッジ時間 4,321 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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