Inclusion-Exclusion Principle: Counting with Overlaps

from math import gcd
from itertools import combinations

def count_divisible(n, nums):
    def lcm(a, b): return a // gcd(a, b) * b

    total = 0
    k = len(nums)
    for size in range(1, k + 1):
        for combo in combinations(nums, size):
            l = combo[0]
            for x in combo[1:]:
                l = lcm(l, x)
            term = n // l
            if size % 2 == 1:
                total += term
            else:
                total -= term
    return total

# LeetCode 2652: Sum Multiples
def sumOfMultiples(n, targets=[3, 5, 7]):
    def sum_div(n, d): return d * (n // d) * (n // d + 1) // 2

    total = sum(sum_div(n, d) for d in targets)
    for i in range(len(targets)):
        for j in range(i+1, len(targets)):
            l = targets[i] * targets[j] // gcd(targets[i], targets[j])
            total -= sum_div(n, l)
    l = targets[0]
    for t in targets[1:]: l = l * t // gcd(l, t)
    total += sum_div(n, l)
    return total

# Derangements: permutations with no fixed point
# D(n) = (n-1) * (D(n-1) + D(n-2))
# D(n) = n! * sum_{k=0}^{n} (-1)^k / k!
# D(n) ≈ n! / e (round to nearest integer)
def derangements(n, mod=10**9+7):
    if n == 0: return 1
    if n == 1: return 0
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 0
    for i in range(2, n + 1):
        dp[i] = (i - 1) * (dp[i-1] + dp[i-2]) % mod
    return dp[n]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// Count integers in [1, n] divisible by at least one element
ll inclusionExclusion(ll n, vector<ll>& nums) {
    int k = nums.size();
    ll total = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        ll l = 1, sign = 1;
        for (int i = 0; i < k; i++) {
            if (mask >> i & 1) {
                l = lcm(l, nums[i]);
                sign = -sign;
            }
        }
        total -= sign * (n / l); // sign starts at 1, toggled per element
    }
    // Correct: count 1s in mask determines sign
    total = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        ll l = 1; int bits = __builtin_popcount(mask);
        for (int i = 0; i < k; i++)
            if (mask >> i & 1) l = lcm(l, nums[i]);
        if (bits % 2 == 1) total += n / l;
        else total -= n / l;
    }
    return total;
}

# Count numbers in [1,n] not divisible by 2 or 3
def coprime_to_6(n):
    return n - n//2 - n//3 + n//6  # I-E

# Euler totient via I-E
def phi_ie(n):
    primes = []
    temp = n
    p = 2
    while p * p <= temp:
        if temp % p == 0:
            primes.append(p)
            while temp % p == 0: temp //= p
        p += 1
    if temp > 1: primes.append(temp)

    result = 0
    for mask in range(1, 1 << len(primes)):
        prod = 1; bits = bin(mask).count('1')
        for i, p in enumerate(primes):
            if mask >> i & 1: prod *= p
        if bits % 2 == 1: result += n // prod
        else: result -= n // prod
    return n - result