Đếm số trong khoảng có GCD lũy thừa thừa số nguyên tố bằng 1 trong C++

Cho hai số start và end đại diện cho khoảng số nguyên dương. Mục tiêu: đếm tất cả số trong khoảng [start, end] có phân tích thừa số nguyên tố sao cho tất cả các thừa số nguyên tố của số đó có lũy thừa mà GCD của chúng bằng 1.

Nếu một số có phân tích: 2^p * 3^q * 5^r ... thì GCD(p, q, r, ...) = 1.

Hiểu qua ví dụ

Ví dụ 1

Đầu vào: start = 1, end = 10

Đầu ra: Số lượng số thỏa mãn: 6

Giải thích: Các số: 2 (2^1), 3 (3^1), 5 (5^1), 7 (7^1), 8 (2^3), 10 (2^1 * 5^1). Tất cả GCD lũy thừa = 1.

Ví dụ 2

Đầu vào: start = 11, end = 20

Đầu ra: Số lượng số thỏa mãn: 9

Giải thích: Các số: 11 (11^1), 12 (3^1 * 2^2), 13 (13^1), 14 (2^1 * 7^1), 15 (3^1 * 5^1), 17 (17^1), 18 (2^1 * 3^2), 19 (19^1), 20 (2^2 * 5^1). GCD lũy thừa = 1.

Phương pháp sử dụng

Đếm tất cả số trong khoảng start đến end không phải là lũy thừa hoàn hảo (perfect powers). Vì các số không phải lũy thừa hoàn hảo sẽ thỏa mãn điều kiện.

Đáp án = start - end + 1 - (số lượng perfect powers trong [start, end]).

Nhập biến khoảng start, end.
Vector vec lưu lũy thừa > 3.
Set sett lưu bình phương hoàn hảo.
Set sett_2 lưu số không phải bình phương hoàn hảo.
Hàm calculate() điền vec, sett, sett_2.
Duyệt i = 2 đến size: chèn i*i vào sett.
Nếu i trong sett (là bình phương hoàn hảo) thì bỏ qua.
Vòng lặp while cho đến khi lũy thừa nhỏ hơn giá trị lớn.
Chèn lũy thừa lẻ vào sett_2 (lũy thừa chẵn đã trong sett).
Cuối cùng chèn giá trị đã sắp xếp của sett_2 vào vec.
Hàm GCD_1(long int start, long int end) trả về số lượng số thỏa mãn.
Gọi calculate().
Tính bình phương hoàn hảo trong khoảng: per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1)).
Tính top, bottom bằng upper_bound, lower_bound trên vec.
Tổng lũy thừa hoàn hảo: per_pow = per_sq + (top - bottom).
Kết quả: count = (end - start + 1) - per_pow.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 
#define size 1000005 
#define large 1e18 

vector<long int> vec; 
set<long int> sett; 
set<long int> sett_2; 

void calculate() { 
    for (long int i = 2; i < size; i++) { 
        sett.insert(i * i); 
        if (sett.find(i) != sett.end()) continue; 
        long int total = i; 
        while (i * i <= large / total) { 
            total *= (i * i); 
            sett_2.insert(total); 
        } 
    } 
    for (auto it : sett_2) vec.push_back(it); 
} 

long int GCD_1(long int start, long int end) { 
    calculate(); 
    long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1)); 
    long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin(); 
    long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin(); 
    long int per_pow = per_sq + (top - bottom); 
    long int count = (end - start + 1) - per_pow; 
    return count; 
} 

int main() { 
    long int start = 10, end = 40; 
    cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7