Inclusion–Exclusion Principle

When conditions overlap, adding their counts double-counts shared objects. Inclusion–exclusion corrects this by alternating intersection counts. It is useful for counting integers divisible by any selected divisor, forbidden patterns and unions of constraints. The program counts values in 1..N divisible by at least one of k positive divisors, using subset masks and LCM-based intersection sizes.

Prerequisites: Combinations; bitmasks; LCM; floor division.

Build the idea

1. 1. Start with two and three sets

   For two sets, |A∪B|=|A|+|B|−|A∩B|. With three, add single counts, subtract all pair intersections, then add the triple intersection back. An element in all three was counted three times, subtracted three times and must be restored once. Mutually exclusive sets have no overlap; general sets require these corrections.

   $$|A\cup B|=\left|A\right|+\left|B\right|-|A\cap B|$$

2. 2. Generalize by subset parity

   For every nonempty subset S of conditions, add its intersection count if |S| is odd and subtract if even. An element satisfying t conditions gets coefficient Σⱼ≥1(−1)^(j+1)C(t,j)=1 from expanding (1−1)^t. Elements satisfying none contribute zero. This proves the alternating formula rather than merely suggesting a pattern.

   $$|\bigcup A_i|=\sum _{S\ne \varnothing }{(-1)}^{\left|S\right|+1}\left|\bigcap _{i\in S}{A}_i\right|$$

3. 3. Convert intersections to arithmetic

   Being divisible by every divisor in S means being divisible by their LCM, so the intersection contains floor(N/LCM(S)) integers. Repeated divisors or one divisor dividing another do not invalidate inclusion–exclusion, although preprocessing redundant conditions can reduce k. Use GCD to form each LCM safely.

4. 4. Trace divisors 2,3,5 up to 20

   Singles contribute 10+6+4=20. Pair intersections use LCMs 6,10,15 and subtract 3+2+1=6. The triple LCM is 30, contributing zero. Total is 14. Simply summing the three individual counts would overcount values such as 6,10,12,15,18 and20.

5. 5. Cap impossible intersections before overflow

   When the next LCM would exceed N, that intersection contributes zero and its exact huge value is unnecessary. Check reduced>N/divisor before multiplying reduced=LCM/gcd(LCM,divisor). Positive divisors make the division valid. k≤20 keeps both mask shifts and the exponential number of subsets manageable; larger k generally needs another structural approach.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Cap impossible intersections before overflow When the next LCM would exceed N, that
// intersection contributes zero and its exact huge value is unnecessary.
#include<iostream>
#include<vector>
#include<numeric>
int main(){
    long long N;
    int k;
    std::cin>>N>>k;
    std::vector<long long>divisors(k);
    for(auto&d:divisors){
        std::cin>>d;
    }
    long long answer=0;
    for(unsigned int mask=1;mask<(1U<<k);++mask){
        long long lcm=1;
        int count=0;
        bool exceeds=false;
        for(int i=0;i<k;++i){
            if(mask&(1U<<i)){
                ++count;
                long long reduced=lcm/std::gcd(lcm,divisors[i]);
                if(reduced>N/divisors[i]){
                    exceeds=true;
                    break;
                }
                lcm=reduced*divisors[i];
            }
        }
        if(!exceeds){
            long long term=N/lcm;
            answer+=(count%2?term:-term);
        }
    }
    std::cout<<answer<<'\n';
}

Complexity analysis

O(2ᵏ·k·log C) is a safe bound including GCD work, C≤10^12, and O(k) input storage with constant subset state. Early capping can reduce actual work but not the exponential worst case. With k≤20 and N≤10^12, even the sum of absolute subset terms stays below about 1.05×10^18, fitting long long.

Example input and output

Read N k, 0≤N≤10^12 and 0≤k≤20, then k divisors in 1..10^12. Print the count of integers in 1..N divisible by at least one divisor.

Input

20 3
2 3 5

Output

14

20 single-condition counts minus 6 pair counts plus zero triple counts gives 14.

Practical applications

Use for unions of a small number of overlapping conditions when intersections are easy to count. If sets are disjoint, simple addition suffices. When intersection counts are hard or k is large, DP, sieves or another combinatorial decomposition may be preferable.

Check your understanding

What counts the intersection of divisibility by a and b?

Put it into practice

Compare against testing every integer for small N, including duplicate divisors.