# Help regarding UVA Question-The Lottery

Problem-Getting TLE

My approach-Calculated LCM of all numbers and tried to find numbers upto that lcm which are not divisible by it and accordingly finding uptil n as a cycle is repeated and remaining are separately counted.

My searches on google-Checked it on github as people have posted solutions there also checked a online forum where this question was discussed. By looking them they have checked j uptil 1<<m and checking for all array values of 1<<i (where i is the index of array) that if j&(1<<i) !=0 execute it.

My question-Why the above process was done. What does this -j&(1<<i) !=0 achieve. Any other way would also be appreciated. Please guys if anybody could explain this would be highly helpful

the above process is based on inclusion exclusion principle

1 Like

Say F(X) → Number multiples of X which are less than N. It’s trivial to see that F(X)=\displaystyle \frac{N}{X}
A_i → Set of all subsequences of size i. So if you apply exclusion-inclusion the problem boils down to finding the following summation.

A=\sum_{i=1}^M\sum_{S \in A_i}\sum_{j \in S}(-1)^{i+1}F(j) \\ A=\sum_{i=1}^M\sum_{S \in A_i}\sum_{j \in S}(-1)^{i+1}\frac{N}{j}

And given the small constraints, you can naively evaluate it in \mathcal{O}(M\times2^M \log A_{max})

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() ;
}



PS: Is this the worst online judge of all time?

1 Like

Thanks a lot both of you. Now the solution has become clear. Thanks

Could you please explain what exactly is (int b) counting and checking for? Thankyou!