Help regarding UVA Question-The Lottery

1

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

2

the above process is based on inclusion exclusion principle
you can read about it here and here.

1 Like
4

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
5

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

6

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