
You are given a natural number N(N \leq10^8), and an array of M integers Arr, task is to find how many numbers from [1,N] is divisible by any of the array elements.

Find kth number (kth number <= N)
I can’t think of a solution which has a better complexity than \mathcal{O}(M\times2^M \log A_{max}), so sharing it won’t be of any help as it is too slow.
Pls share
Do you have the constraints on M ?
No
Assume m<=10
Is it based on inclusion exclusion principle , with Binary searching the answer?
Assuming you’re familiar with inclusionexclusion principle, say \displaystyle D(X)=\frac{N}{X} → Number of multiples of X which are less than or equal to N
And S_i → set of all subsets of size i. On applying inclusion exclusion final answer X could be written as.
CODE
#include "bits/stdc++.h"
#define int long long
using namespace std ;
int lcm(int x,int y){
return (x*y)/__gcd(x,y) ;
}
int n,m ;
void solve(){
cin >> m ;
vector<int>a(m) ;
for(int &x:a)
cin >> x ;
int ans =0 ;
for(int i=0;i<(1<<m);i++){
int j=0,b=0,c=i,l=1 ;
while(c){
if(c&1)
b++,l=lcm(l,a[j]) ;
c>>=1 ;j++ ;
}
ans+=n/l*(b&1?1:1) ;
}
cout << ans << '\n' ;
}
signed main(){
while(cin>>n)
solve() ;
}
Putting above expression in words would translate to summing up all N/j lcm of all subsequences of size 1  N/lcm of all subsequences of size 2 + sum of N/lcm of all subsequences of size 3…
Yes but I’m not exactly sure on what would you binary search on, can you elaborate ?
Time complexity : O( M 2^M * Log (N) )
Quick explanation :
Binary search the kth element on [1,N] ,
Process of how to check if no. of factors is less than or equal to or greater than K:
Consider all subsets of A[i] no.s , if the subset contains even no. of elements then we can substract mid/(LCM(all element in subset)) else we can add all mid/(LCM(all element in subset ))
It is based on the fact that S(AUBUC)=S(A)+S(B)+S( C )S(A intersection B)S(B intersection C)  S ( A intersection C) + S ( A intersection B intersection C)
We have to check all subset of size i right ?
how is this doing ?
Oh… you meant for the second part, t, I thought you were talking about finding number of such numbers in range 1N, yes we’ll have to binary search the answer
You’ll have to iterate over all subsets of all sizes → just iterate over all subsets.
Ok , that can be done as you said
Do you know bitmasking ?
basic
Well then in iterating from [0,(1<<m)] you can consider all the subsets of m elements . And then he is just checking that the i’th bit is set or not ( he is checking that by doing c>>=1 and then C&1 , you can check it by C&(1<<j)) which denotes that current set has i’th element or not
thanks I got that part. Can you little explain more about binary search
We are checking that how many no. Which are smaller than middle element are divisible by any of the elements of array , if they are equal to k then we will make it high=mid1 as we want to find the smallest no. For which there are k no. Less than equal to mid.
Just out of curiosity, willn’t Sieve work here?