Help in this problem

help
1

  1. 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.

  2. Find kth number (kth number <= N)

2

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.

3

Pls share

4

Do you have the constraints on M ?

5

No

Assume m<=10

6

Is it based on inclusion exclusion principle , with Binary searching the answer?

7

Assuming you’re familiar with inclusion-exclusion 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.

X=\sum_{i=1}^M\sum_{S \in S_i}\sum_{j \in S}(-1)^{i+1}D(j) \\ X=\sum_{i=1}^M\sum_{S \in S_i}\sum_{j \in S}(-1)^{i+1}\frac{N}{j}
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…

2 Likes
8

Yes but I’m not exactly sure on what would you binary search on, can you elaborate ?

9

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)

1 Like
10

We have to check all subset of size i right ?

how is this doing ?

11

Oh… you meant for the second part, t, I thought you were talking about finding number of such numbers in range 1-N, yes we’ll have to binary search the answer

12

You’ll have to iterate over all subsets of all sizes → just iterate over all subsets.

13

Ok , that can be done as you said :slight_smile:

1 Like
14

Do you know bitmasking ?

15

basic

16

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

1 Like
17
1 Like
18

thanks I got that part. Can you little explain more about binary search

19

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=mid-1 as we want to find the smallest no. For which there are k no. Less than equal to mid.

1 Like
20

Just out of curiosity, willn’t Sieve work here?