Submission #3644845


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
using ll = long long int;

const ll INF = 1LL << 50;
int main(){
    ll N, Q; cin >> N >> Q;

    vector<ll> nums(Q);
    for(int i=0; i<Q; i++) {
        cin >> nums[i];
    }

    set<ll> ans;
    for(int bit=0; bit<(1<<Q); bit++) {
        ll mul = 1, valid = true;
        for(int i=0; i<Q; i++) {
            if(bit >> i & 1) {
                mul *= nums[i];
                if(mul > INF) {
                    valid = false;
                    break;
                }
            }
        }

        if(valid and mul <= N) {
            ll num = mul;
            for(int i=0; i<Q; i++) {
                if(mul % nums[i] == 0) mul /= nums[i];
            }

            if(mul == 1) ans.insert(num);
        }
    }
    cout << ans.size() << endl;
    return 0;
}

Submission Info

Submission Time
Task B - Division 2
User tsutaj
Language C++14 (GCC 5.4.1)
Score 100
Code Size 910 Byte
Status AC
Exec Time 2236 ms
Memory 2688 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 3 ms 256 KB
sub1_6.txt AC 3 ms 256 KB
sub2_1.txt AC 5 ms 256 KB
sub2_2.txt AC 5 ms 384 KB
sub2_3.txt AC 8 ms 384 KB
sub2_4.txt AC 6 ms 384 KB
sub2_5.txt AC 181 ms 640 KB
sub2_6.txt AC 203 ms 640 KB
sub2_7.txt AC 2126 ms 1152 KB
sub2_8.txt AC 2236 ms 2688 KB