Help regarding UVA Question-The Lottery

Here’s the question link-question

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 code-code (I have added comments where solution starts and ends)

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
you can read about it here and here.

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

#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 ;
				b++,l=lcm(l,a[j]) ;
			c>>=1 ;j++ ;
		ans+=n/l*(b&1?-1:1) ;
	cout << ans << '\n' ;
signed main(){		
		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 :grin:

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