Nguyên lý bù trừ (Inclusion-Exclusion)

Đề bài: Cho số n, in ra số các số trong đoạn [1;n] chia hết cho 1 trong 4 số: 2,3,11,13.
Lời giải:
#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <class T> T gcd (T a, T b) {  while (b) { T r = a % b; a = b; b = r; } return a; }
template <class T> T lcm (T a, T b) { return a / gcd (a, b) * b; }

long long sum=0;
long long  num;

void solve(vector<long long> & v){
int N=v.size();

for(int i=1;i<(1<<N);i++){
    ll ct=1;
    for(int k=0;k<N;k++)if( i & (1<<k) ) ct=lcm(ct,v[k]);
        if(1 & __builtin_popcount(i))sum+=num/ct;
            else sum-=num/ct;
        }
    }

int main(){
    vector<long long> v={2,3,11,13};
    cin>>num;
    solve(v);
    ll res=gcd(sum,num);
    cout<<sum/res<<' '<<num/res;
    return 0;
    }