BÀI G

MAY QUÁ KHÔNG AI GIẢI RA BÀI NÀY

Trước hết, mình hi vọng không ai A/C để ami được vui mừng :D.

Với những bài tìm số lớn thứ \(c\) của một dãy số như thế này, các bạn có thể dùng thuật toán chặt nhị phân.

Gọi \(x\) là kết quả của bài toán và hàm \(D(t)\) là số các số tự nhiên \(y\) thỏa mãn :

• \(y \le t\)
• GCD\((y,b) = 1\).

Vậy \(D(x) – D(a) = c\) và \(x\) là nhỏ nhất có thể.

Ta có thể tính sẵn \(P = D(a)\). Ta chặt nhị phân số \(x\), và tính hàm \(D(x)\). Nếu \(D(x) – P \ge c\), ta sẽ lưu lại kết quả và giảm cận phải lại, ngược lại ta lại tăng cận trái :

        Int phải = 10 mũ 9 , trái = 1 ;

        While (phải >= trái)
        {
                    Int x = (phải + trái) / 2 ;

                    If (D(x) – P >= c) result = x , phải = x – 1 ;

                    Else trái = x + 1;
        }

Rõ ràng sau hàm chặt nhị phân này, ta sẽ tìm được kết quả. Vấn đề cuối cùng là làm sao để tính được \(D(x)\) trong thời gian cho phép ? Ở đây mình sẽ dùng lí thuyết bao hàm loại trừ.

Giả sử số \(x\) có \(P_1,P_2,P_3,…,P_K\) là các ước số nguyên tố. Từ các ước nguyên tố, ta có thể sinh ra tất cả các số \(S_1,S_2,…,S_G\) với \(S_i\) được tạo ra bằng tích của một hay nhiều số \(P_i\) và mỗi số \(P_i\) chỉ được dùng tối đa một lần. Vậy dãy \(S\) sẽ có khoảng \(2^K\) số. Từ đó, số các số nguyên tố cùng nhau với \(x\) và nhỏ hơn \(x\) sẽ bằng \(x + cnt\) với :

• cnt -= x / S[i] nếu \(S_i\) là tích của lẻ số trong dãy \(P\).
• cnt += x / S[i] nếu \(S_i\) là tích của chẵn số trong dãy \(P\).

Với mọi \(S_i\) có thể tạo ra từ dãy \(P\), ta sẽ tính \(cnt\) theo công thức trên.

Nhận thấy rằng một số nguyên \(n\) sẽ không có quá \(2\sqrt{n}\) ước, vì vậy độ phức tạp cho mỗi query tối đa sẽ là \(O(log(n) \times \sqrt{n})\).

Credit :

Bài này là một bài trên Codeforces.

Cảm ơn anh CaiWinDao đã phổ cập cho mình lí thuyết bao hàm loại trừ.