Submission #3696916


Source Code Expand

import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    auto nq = reads!long;
    long n = nq[0], q = nq[1];
    int[] a;
    for (int i = 0; i < q; i++) a ~= readint;

    bool[long] set;
    for (int i = 0; i < (1 << q); i++) {
        long x = 1;
        bool valid = true;
        for (int j = 0; j < q; j++) {
            if (i & (1 << j)) {
                x *= a[j];
                if (x > n) {
                    valid = false;
                    break;
                }
            }
        }

        if (valid) {
            long y = x;
            for (int j = 0; j < q; j++) {
                if (y % a[j] == 0) y /= a[j];
            }

            if (y == 1) set[x] = true;
        }
    }

    auto ans = set.keys.count;
    writeln(ans);
}

Submission Info

Submission Time
Task B - Division 2
User noriok
Language D (DMD64 v2.070.1)
Score 100
Code Size 1069 Byte
Status AC
Exec Time 2301 ms
Memory 3836 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 25 / 25 75 / 75
Status
AC × 4
AC × 10
AC × 18
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt
Subtask1 sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 1 ms 256 KB
sub1_1.txt AC 1 ms 256 KB
sub1_2.txt AC 1 ms 256 KB
sub1_3.txt AC 1 ms 256 KB
sub1_4.txt AC 1 ms 256 KB
sub1_5.txt AC 2 ms 256 KB
sub1_6.txt AC 2 ms 256 KB
sub2_1.txt AC 6 ms 380 KB
sub2_2.txt AC 5 ms 508 KB
sub2_3.txt AC 8 ms 508 KB
sub2_4.txt AC 6 ms 508 KB
sub2_5.txt AC 188 ms 3196 KB
sub2_6.txt AC 208 ms 1020 KB
sub2_7.txt AC 2284 ms 3324 KB
sub2_8.txt AC 2301 ms 3836 KB