47's Task

Once Agent 47's handler 'Diana' became angry with him and gave him a task.

Given a number "N" and an array 'A' of size 'P', agent 47 has to tell the count of total numbers in the range [1,N], which are divisible by any of the array elements.

Since, Agent 47 is not very great at Mathematics, he asks for your help.

Example:

Input:  n = 15, p = 3, v = {2, 3, 5}
Output: 11

Approach

C++

#include <bits/stdc++.h>
using namespace std;

void fourtySevenTask(long long n, long long p,
                     vector<long long> &v)
{

    map<long long, long long> m;
    for (long long i = 0; i < p; i++)
    {
        m[v[i]] = 1;
    }
    p = m.size();
    long long kk = 0;
    for (auto it = m.begin(); it != m.end(); it++)
        v[kk++] = it->first;
    long long ans = 0;
    for (long long i = 1; i < (1 << p); i++)
    {
        long long pro = 1;
        long long sign = -1;
        for (long long j = 0; j < p; j++)
        {
            if ((i >> j) & 1)
            {
                pro *= v[j];
                sign *= -1;
            }
        }

        if (sign == 1)
            ans += (n / pro);
        else
            ans -= (n / pro);
    }
    cout << ans << "\n";
}
int main()
{

    long long n = 15, p = 3;

    vector<long long> v = {2, 3, 5};

    fourtySevenTask(n, p, v);

    return 0;
}