XMASGIFT : Santa gives gifts

In this blog, we will look at how you could approach the problem “Santa gives gifts” in The Coding Culture’s December Contest “Number Quest”.

Contest Page | CodeChef

Mathematics behind the problem

This problem, in the end, boils down to being able to count without overcounting, Let’s see what I mean by this

Say you want to find number of numbers that are divisible by 5 from 1 to 50; well, clearly anyone would say its 10, right? well, all you did was divide 50 by 5 right. In fact, its works with all numbers, for example, number of numbers that are divisible by 7 from 1 to 50 is floor(50/7) = 7.

Now say you want to find number of numbers that are divisible by either 3 or 5 from 1 to 50. Then could you add up floor(50/3) and floor(50/5). Well, if you think about it, not quite, you’d be counting numbers that are both divisible by 3 and 5 (such as 15, 30, 45) twice right? so you need to correct for that by number of numbers that are both divisible by 3 and 5 right. A generalized version of this is called principle of inclusion-exclusion in mathematics. You might have seen it before in your set theory class as

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

where A = {elements divisible by 3}, B = {elements divisible by 5}.

Now the natural question that arises would be how to calculate n(A ∩ B), ie, how to find the number of numbers that are both divisible by A and B. Well, we use the least common multiple of the two numbers, then we know that all multiples of the LCM will occur in both their multiples. So we can infer,
n(A ∩ B) = 50/LCM(3,5), so then we can say, the number of numbers that are not divisible by 3 or 5 = 50-floor(50/3)-floor(50/5)+floor(50/lcm(3,5))

Now, we can use the general principal of inclusion-exclusion to infer that, given numbers 1 to k, the number of numbers divisible by a1, a2, a3, a4, a5 is

where A_i is a subset containing i elements; This allows us to solve the problem in O(number of subsets of 5 elements) = O(2⁵)

Generating the subsets

There are multiple ways you can generate the subsets. One through bit manipulation and the other through recursion. Resources to both are linked below.

Find all distinct subsets of a given set — GeeksforGeeks

Backtracking to find all subsets — GeeksforGeeks

Solution

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ap[5];
inline ll lcm(ll a, ll b) {
    return (a/__gcd(a, b))*b;
}
ll cnt(ll i, ll count, ll n, ll lcm_of_subset) {
    if (i == 5) {
        if (count % 2 == 0)
            return n/lcm_of_subset;
        else
            return -n/lcm_of_subset;
    }
ll result = 0;
    result += cnt(i + 1, count, n, lcm_of_subset);
    result += cnt(i + 1, count+1, n, lcm(lcm_of_subset, ap[i]));
return result;
}
void solve() {
    ll n, m, a, d;
    cin >> n >> m >> a >> d;
    for (int i = 0; i < 5; i++)
        ap[i] = a + i*d;
    
    cout << cnt(0, 0, m, 1) - cnt(0, 0, n-1, 1) << endl;
}
int main() {
    ll t;
    cin >> t; 
    while (t--)
        solve();
    return 0;
}