結果

問題 No.3039 April Fool Tekitou
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-01-13 07:26:21
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,854 bytes
コンパイル時間 1,571 ms
コンパイル使用メモリ 158,228 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-09-03 22:04:28
合計ジャッジ時間 2,124 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


immutable LIM = 3 * 10L^^10;
immutable DATA = [
24,24,4,16,80,12,32,16,24,12,96,8,32,4,96,2,48,16,4,80,24,16,16,8,48,32,8,2,48,8,16,16,12,4,48,8,60,24,8,8,48,4,8,16,16,4,64,8,12,32,8,2,160,4,96,12,12,4,64,6,8,16,16,24,72,4,8,16,10,16,32,16,12,16,8,4,64,32,16,32,48,8,12,2,192,4,8,8,48,16,4,24,16,8,32,6,24,32,16,4 
];

int numDivisors(long n) {
  int ret = 1;
  foreach (p; smallPrimes) {
    if (n % p == 0) {
      int e;
      do {
        n /= p;
        ++e;
      } while (n % p == 0);
      ret *= (e + 1);
    }
  }
  if (n > 1) {
    ret *= (1 + 1);
  }
  return ret;
}

bool check(long x) {
  if (!(1 <= x && x <= LIM)) {
    return false;
  }
  foreach (k; 0 .. DATA.length) {
    if (numDivisors(x + k) != DATA[k]) {
      return false;
    }
  }
  return true;
}

int[] smallPrimes;
long[] ans;

// Find primes <= lim
//   isComposite[k][i]: (30 (offset + k) + D[i]) is composite
void sieve(long lim) {
  enum SMALL_LIM = 2 * 10^^5;
  enum SIEVE_LENGTH = 10^^6;
  enum D = [1, 7, 11, 13, 17, 19, 23, 29];
  enum POS = [
    -1, 0, -1, -1, -1, -1,
    -1, 1, -1, -1, -1, 2,
    -1, 3, -1, -1, -1, 4,
    -1, 5, -1, -1, -1, 6,
    -1, -1, -1, -1, -1, 7,
  ];
  enum INV = [
    0, 1, 0, 0, 0, 0,
    0, 13, 0, 0, 0, 11,
    0, 7, 0, 0, 0, 23,
    0, 19, 0, 0, 0, 17,
    0, 0, 0, 0, 0, 29,
  ];

  assert((cast(long)(SMALL_LIM))^^2 > lim);
  // int[] smallPrimes;
  auto isCompositeSmall = new bool[SMALL_LIM];
  foreach (p; 2 .. SMALL_LIM) {
    if (!isCompositeSmall[p]) {
      smallPrimes ~= p;
      for (int q = 2 * p; q < SMALL_LIM; q += p) {
        isCompositeSmall[q] = true;
      }
    }
  }

  // auto isComposite = new ubyte[SIEVE_LENGTH];
  auto isComposite = new ubyte[SIEVE_LENGTH + 10];
  for (long offset = 0; 30 * offset <= lim; offset += SIEVE_LENGTH) {
    stderr.writefln("30 * offset = %s", 30 * offset);
    isComposite[] = 0u;
    foreach (p; smallPrimes) {
      if (p > 5) {
        foreach (i, d; D) {
          long k = (((d * INV[p % 30]) % 30) * p - d) / 30;
          if (30 * k + d == p) {
            k += p;
          }
          if (k < offset) {
            k += (offset - k + p - 1) / p * p;
          }
          // for (k -= offset; k < SIEVE_LENGTH; k += p) {
          for (k -= offset; k < SIEVE_LENGTH + 10; k += p) {
            isComposite[cast(size_t)(k)] |= 1u << i;
          }
        }
      }
    }
    bool isPrime(long n) {
      const j = POS[cast(size_t)(n % 30)];
      return (j >= 0 && !((isComposite[cast(size_t)(n / 30 - offset)] >> j) & 1));
    }
    foreach (k; 0 .. SIEVE_LENGTH) {
      foreach (i, d; D) {
        //
        if (d != 11) continue;
        //
        if (!((isComposite[k] >> i) & 1)) {
          const p = 30 * (offset + k) + d;
          // p is 1 or prime > 5
          if (5 < p && p < lim) {
            //
            if (isPrime(p + 12) && isPrime(p + 36) && isPrime(p + 68)) {
              if (check(p - 15)) {
                stderr.writefln("  found p = %s", p);
                ans ~= p - 15;
              }
            }
            //
          }
        }
      }
    }
  }
}

void main() {
  stderr.writefln("|DATA| = %s", DATA.length);
  foreach (k; 0 .. DATA.length) {
    if (DATA[k] % 2 != 0 || DATA[k] == 2) {
      stderr.writefln("DATA[%s] = %s", k, DATA[k]);
    }
  }
  // p (= x + 21), p + 12, p + 36, p + 68 are primes
  
  foreach (d; 0 .. 30) {
    bool ok = true;
    foreach (k; 0 .. DATA.length) {
      int cnt;
      if ((d + k) % 2 == 0) ++cnt;
      if ((d + k) % 3 == 0) ++cnt;
      if ((d + k) % 5 == 0) ++cnt;
      ok = ok && (DATA[k] > 1 << cnt);
    }
    if (ok) {
      stderr.writefln("d = %s, d + 15 == %s", d, (d + 15) % 30);
    }
  }
  // too small or p == 11 (30)
  
  // ~ 6 minutes :(
  // sieve(LIM + 100);
  // writeln(ans);
  
  writeln(20170387916);
}
0