Tìm số phép toán tối đa để giảm N về 1 trong C++

Khái niệm

Cho hai số P và Q (P và Q có thể lên tới 10^6) tạo thành số N = (P!/Q!). Nhiệm vụ là giảm N về 1 bằng cách thực hiện số phép toán tối đa có thể. Nhớ rằng, trong mỗi phép toán, ta có thể thay thế N bằng N/X nếu N chia hết cho X. Xác định số phép toán tối đa có thể thực hiện.

Đầu vào

A = 7, B = 4

Đầu ra

Giải thích

N là 210 và các ước số là 2, 3, 5, 7

Đầu vào

A = 3, B = 1

Đầu ra

Giải thích

N là 6 và các ước số là 2, 3.

Phương pháp

Đã quan sát thấy rằng phân tích thừa số nguyên tố của P!/Q! giống với phân tích thừa số nguyên tố của các số (Q + 1)*(Q + 2)*...*(P - 1)*P.

Số phép toán sẽ tối đa nếu ta chỉ chia N cho các thừa số nguyên tố của nó. Nói cách khác, ta cần đếm số thừa số nguyên tố của N (bao gồm cả thừa số trùng lặp).

Giả sử đếm số thừa số nguyên tố trong phân tích của mọi số từ 2 đến 1.000.000.

Trước tiên, triển khai Sàng Eratosthenes để tìm ước số nguyên tố của mỗi số. Quy trình như sau:

Xây dựng danh sách các số nguyên liên tiếp từ 2 đến N: (2, 3, 4, ..., N).
Đầu tiên, giả sử p = 2, số nguyên tố đầu tiên.
Bắt đầu từ p^2, đếm theo bước nhảy p và đánh dấu các số lớn hơn hoặc bằng p^2. Các số này có dạng p(p+1), p(p+2), p(p+3), v.v.
Tìm số đầu tiên lớn hơn p trong danh sách chưa bị đánh dấu. Nếu không có số như vậy, dừng lại. Ngược lại, gán p bằng số này (số nguyên tố tiếp theo) và lặp lại từ bước 3.

Sau khi áp dụng Sàng Eratosthenes, ta có thể tính số thừa số nguyên tố trong phân tích của một số bằng công thức:

primefactors[num] = primefactors[num / primedivisor[num]] + 1

Hiện tại, ta có thể xây dựng mảng tiền tố cho thừa số nguyên tố và trả lời tổng trên khoảng [P, Q].

Ví dụ

// Chương trình C++ tìm số phép di chuyển tối đa có thể
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Lưu số thừa số nguyên tố của mỗi số
int primeFactors1[N];

// Hàm tìm số thừa số nguyên tố của mỗi số
void findPrimeFactors(){
    for (int a = 2; a < N; a++)
        // Nếu a là số nguyên tố
        if (primeFactors1[a] == 0)
            for (int b = a; b < N; b += a)
                // Tăng giá trị lên 1 từ bội số trước đó
                primeFactors1[b] = primeFactors1[b / a] + 1;
    // Xây dựng mảng tiền tố
    // Hữu ích cho nhiều trường hợp test
    for (int a = 1; a < N; a++)
        primeFactors1[a] += primeFactors1[a - 1];
}

// Chương trình chính
int main(){
    // Tạo mảng primeFactors1
    findPrimeFactors();
    int P = 7, Q = 4;
    // Đáp án yêu cầu
    cout << primeFactors1[P] - primeFactors1[Q];
    return 0;
}