Алгоритм, который находит n-е число взаимно простым с данным (включение - принцип исключения)

Question

Я столкнулся с проблемой, которая просит меня найти n-й номер, который взаимно прост с данным (p).

Ограничения:

• 1 ≤ n ≤ 12 000 000 000
• 1 ≤ p ≤ 10 ^ 14
• Ограничение по времени: 0,05 секунды

Сейчас ожидаемое решение использует принцип включения и исключения. У других, которые решили эту проблему, есть функция, которую я не могу понять, что она делает, но я знаю, что она должна использовать этот принцип. Если кто-то может объяснить функцию, это было бы здорово.

Вот полный источник от кого-то, кто решил эту проблему:

#include <cmath>
#include <vector>
#include <bitset>
#include <climits>
#include <fstream>
#include <iostream>
using namespace std;
const int NMAX = 11e4 ;
bitset < NMAX + 5 > c ;
vector < int > primes ;
inline void sieve ( long long n ) {
    long long i, j, lim = ( long long ) sqrt ( ( double ) n ) ;
    c [ 0 ] = c [ 1 ] = 1 ;
    for ( i = 4 ; i <= n ; i += 2 )
        c [ i ] = 1 ;
    for ( i = 3 ; i <= lim ; i += 2 )
        if ( ! c [ i ] )
            for ( j = i * i ; j <= n ; j += i * 2 )
                c [ j ] = 1 ;
    primes.reserve ( 1e4 ) ;
    primes.push_back ( 2 ) ;
    for ( i = 3 ; i <= n ; i += 2 )
        if ( !  c [ i ] )
            primes.push_back ( i ) ;
}
long long factors [ 25 ], nr, med ;
inline void gen_fact ( long long x ) {
    long long d = 0, ok ;
    nr = 0 ;
    while ( primes [ d ] * primes [ d ] <= x && d < primes.size () ) {
        ok = 0 ;
        while ( x % primes [ d ] == 0 )
            x /= primes [ d ], ok = 1 ;
        if ( ok )
            factors [ ++ nr ] = primes [ d ] ;
        ++ d ;
    }
    if (x != 1)
        factors [++nr] = x;
}

inline long long numbers(long long x) {
    long long p, sign, i, j, cnt, ans = x ;
    for ( i = 1 ; i < ( 1 << nr ) ; ++ i ) {
        sign = 1 ;
        p = 1 ;
        cnt = 0 ;
        for ( j = 0 ; j < nr ; ++ j )
            if ( ( 1 << j ) & i ) {
                p *= factors [ j + 1 ] ;
                ++ cnt ;
            }
        if ( cnt % 2 )
            sign = - 1 ;
        ans += sign * x / p ;
    }
    return ans ;
}

int main() {
    ifstream in ( "frac.in" ) ;
    ofstream out ( "frac.out" ) ;
    long long n, p, st, dr, last, val ;
    sieve( NMAX ) ;
    in >> n >> p ;
    gen_fact ( n ) ;
    st = 0 ;
    dr = LLONG_MAX ;
    while ( st <= dr ) {
        med = ( st + dr ) >> 1 ;
        val = numbers ( med ) ;
        if ( val >= p )
            dr = med - 1, last = med ;
        else
            st = med + 1 ;
    }
    out << last ;
}

Рассматриваемая функция - numbers().

Что касается других функций, я их понимаю. Единственное объяснение, которое мне нужно, это то, как эта функция использует принцип включения-исключения.

В комбинаторике принцип включения-исключения является методом подсчета, который обобщает известный метод получения числа элементов в объединении. из двух конечных множеств; символически выражается как Wikipedia MathJax визуализация выражения .

Полная идентичность: Wikipedia MathJax визуализация личности

Что касается того, что я узнаю в функция, использующая принцип, линия ans += sign * x / p - это единственное, что я узнаю.

Из этого принципа я понимаю, что способ найти элементы воссоединения множеств состоит в том, чтобы добавить все элементы каждого отдельного набора в один большой набор, затем из этого большого набора вычтите элементы, которые имеют 2 общих произвольных набора из указанных, затем добавьте элементы, которые имеют общие 3 произвольных набора, и так далее. Это связано с тем, что в первый раз, когда мы добавили все элементы, мы также добавили элементы, которые также могут быть по крайней мере в другом наборе, которое у нас есть, и при воссоединении мы хотим, чтобы они появлялись только один раз.