Submission #20875614


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, 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; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


enum N = 20;
enum PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71];

void main() {
  try {
    for (; ; ) {
      const A = readLong();
      const B = readLong();
      
      auto dp = new long[1 << N];
      dp[0] = 1;
      foreach (x; A .. B + 1) {
        int q;
        foreach (i; 0 .. N) {
          if (x % PRIMES[i] == 0) {
            q |= 1 << i;
          }
        }
        foreach_reverse (p; 0 .. 1 << N) {
          if (!(p & q)) {
            dp[p | q] += dp[p];
          }
        }
      }
      
      const ans = dp.sum;
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task F - Coprime Present
User hos_lyric
Language D (LDC 1.20.1)
Score 600
Code Size 1866 Byte
Status AC
Exec Time 70 ms
Memory 11404 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 70 ms 11236 KB
hand_02.txt AC 68 ms 11276 KB
hand_03.txt AC 68 ms 11260 KB
random_01.txt AC 16 ms 11224 KB
random_02.txt AC 60 ms 11264 KB
random_03.txt AC 68 ms 11404 KB
random_04.txt AC 40 ms 11392 KB
random_05.txt AC 52 ms 11312 KB
random_06.txt AC 67 ms 11160 KB
random_07.txt AC 30 ms 11268 KB
random_08.txt AC 50 ms 11256 KB
random_09.txt AC 67 ms 11164 KB
random_10.txt AC 46 ms 11364 KB
random_11.txt AC 62 ms 11288 KB
random_12.txt AC 68 ms 11272 KB
random_13.txt AC 29 ms 11160 KB
random_14.txt AC 45 ms 11248 KB
random_15.txt AC 69 ms 11248 KB
random_16.txt AC 23 ms 11268 KB
random_17.txt AC 51 ms 11224 KB
random_18.txt AC 66 ms 11248 KB
random_19.txt AC 39 ms 11228 KB
random_20.txt AC 63 ms 11264 KB
random_21.txt AC 67 ms 11264 KB
random_22.txt AC 41 ms 11384 KB
random_23.txt AC 60 ms 11268 KB
random_24.txt AC 66 ms 11228 KB
random_25.txt AC 33 ms 11364 KB
random_26.txt AC 63 ms 11368 KB
random_27.txt AC 67 ms 11224 KB
random_28.txt AC 38 ms 11356 KB
random_29.txt AC 53 ms 11132 KB
random_30.txt AC 68 ms 11336 KB
sample_01.txt AC 18 ms 11400 KB
sample_02.txt AC 20 ms 11268 KB
sample_03.txt AC 56 ms 11204 KB