Let \(E := \{E_1, E_2, \ldots, E_N\}\) be set of event where \(E_i\) is the event that \(x\) is multiple of \(A_i\), and \(g(F)\) \((F \subseteq E)\) be the number of \(x (1 \leq x \leq Y)\) such that all events in \(F\) hold.

For any \(F := \{E_{i_1}, E_{i_2}, \dots, E_{i_k}\}\), It’s easy to see that \(g(F) = \lfloor\frac{y}{LCM(A_{i_1}, A_{i_2}, \ldots, A_{i_k})}\rfloor\).

Now we know how to count number of ways where certain subset of events hold, and we want to count number of ways exactly \(M\) events hold, which can be done by the generalized inclusion-exclusion principle.

The generalized inclusion-exclusion principle

Let \(E := \{E_1, E_2, \ldots, E_N\}\) be the set of event, and \(g(F)\) \((F\subseteq E)\) be the number of ways where all events in \(F\) holds. Then the number of ways exactly \(M\) events hold is given by

\[\sum\limits_{F \subseteq E}g(F)\binom{|F|}{M}(-1)^{|F| - M}\]

Proof: Let’s consider how many times an outcome satisfy exactly all event in \(H \subseteq E\) would be counted. Which is

\[\sum\limits_{F\subseteq H} \binom{|F|}{M}(-1)^{|F| - M} =\sum\limits_{f = 0}^{|H|}\binom{|H|}{f}\binom{f}{M}(-1)^{f - M}\]

The formula on the RHS can be explained as counting number of ways to pick a size \(f\) subset \(F \subseteq H\), then pick another size \(M\) subset \(K \subseteq F\), with multiplicity \((-1)^{f - M}\), and sum over all \(f\).

But we can also pick \(M\) elements belong to \(K\) first, then pick \(f - M\) elements belongs to \(F \setminus K\), with multiplicity \((-1)^{|F \setminus K|}\). which gives

\[\sum\limits_{f = 0}^{|H|}\binom{|H|}{f}\binom{f}{M}(-1)^{f - M} = \binom{|H|}{M}\sum\limits_{j = 0}^{|H| - M}\binom{|H| - M}{j}(-1)^j \\= \binom{|H|}{M}[|H| = M] = [|H| = M]\]

Which means only outcome satisfy exactly \(M\) events would be counted, and this complete the prove.

So using the result above, we can solve the problem by computing the above formula explicitly in \(O(2^N N\lg Y)\). Calculating everyting under\(\pmod {2^{64}}\) using unsigned long long would make the implementation easier.

The submission