นับตัวเลขในช่วงที่ GCD ของกำลังของเฉพาะตัวประกอบเท่ากับ 1 ใน C++

กำหนดสองตัวเลข start และ end แทนช่วงของจำนวนเต็มบวก เป้าหมายคือหาจำนวนตัวเลขทั้งหมดที่อยู่ในช่วง [start, end] และมีการแยกตัวประกอบเฉพาะอย่างที่กำลังของเฉพาะตัวประกอบทั้งหมดมี GCD เท่ากับ 1

ถ้าตัวเลขมีการแยกตัวประกอบเฉพาะเป็น 2^p * 3^q * 5^r ... แล้วกำลัง p, q, r ... ควรจะมี gcd = 1

ทำความเข้าใจด้วยตัวอย่าง

ตัวอย่าง

Input - start = 1, end = 10

Output - จำนวนตัวเลขในช่วงที่ GCD ของกำลังของเฉพาะตัวประกอบเท่ากับ 1 คือ: 6

คำอธิบาย - ตัวเลขคือ:

2 (2¹), 3 (3¹), 5 (5¹), 7 (7¹), 8 (2³) และ 10 (2¹*5¹) กำลังของเฉพาะตัวประกอบแต่ละตัวมี gcd เท่ากับ 1

Input - start = 11, end = 20

Output - จำนวนตัวเลขในช่วงที่ GCD ของกำลังของเฉพาะตัวประกอบเท่ากับ 1 คือ: 9

คำอธิบาย - ตัวเลขคือ:

11 (11¹), 12 (3¹*2²), 13 (13¹), 14 (2¹*7¹), 15 (3¹*5¹), 17 (17¹), 18 (2¹*3²), 19 (19¹) และ 20 (2²*5¹) กำลังของเฉพาะตัวประกอบแต่ละตัวมี gcd เท่ากับ 1

แนวทางที่ใช้ในโปรแกรมด้านล่าง

ในแนวทางนี้ เราจะนับตัวเลขทั้งหมดในช่วง start ถึง end ที่ไม่ใช่ perfect power เนื่องจาก non-perfect powers จะทำให้เงื่อนไขข้างต้นเป็นจริง สำหรับนี้ เราจะหา perfect powers ทั้งหมดและลบออกจากจำนวนรวม

คำตอบ = start - end + 1 - (จำนวนตัวเลขในช่วง [start, end] ที่เป็น perfect powers)

• รับตัวแปรช่วง start และ end เป็นอินพุต
• รับ vector vec เก็บกำลังที่มากกว่า 3
• รับ set sett เก็บตัวเลขที่เป็น perfect squares
• รับ set sett_2 เก็บตัวเลขที่ไม่ใช่ perfect squares
• ฟังก์ชัน calculate() เติม vector vec และ set sett, sett_2 เพื่อแยกตัวเลขที่เป็น perfect squares, non-perfect squares และกำลัง > 3
• วนลูป for จาก i = 2 ถึง i < size
• เพิ่ม perfect powers i*i เข้า sett
• IF sett.find(i) != sett.end() คืนค่า true แล้ว i เป็น perfect square อยู่ใน sett แล้ว ข้ามไป
• รัน while loop จนกว่ากำลังของตัวเลขปัจจุบันจะน้อยกว่า large
• เพิ่มกำลังคี่เข้า sett_2 เพราะกำลังคู่เป็น perfect squares อยู่ใน sett แล้ว
• ในที่สุด ใส่ค่าที่เรียงแล้วของ sett_2 เข้า vector vec ด้วย for loop
• ฟังก์ชัน GCD_1(long int start, long int end) รับช่วงเป็นอินพุตและคืนค่าจำนวนตัวเลขในช่วงที่ GCD ของกำลังของเฉพาะตัวประกอบเท่ากับ 1
• เรียก calculate()
• คำนวณ perfect squares ในช่วง per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1))
• คำนวณค่าบนของ start ใน vec ด้วย upper_bound(vec.begin(), vec.end(), end) - vec.begin()
• คำนวณค่าล่างของ end ใน vec ด้วย lower_bound(vec.begin(), vec.end(), start) - vec.begin()
• คำนวณ perfect powers per_pow = per_sq + (top - bottom)
• คำตอบคือ count = (end - start + 1) - per_pow
• คืนค่า count เป็นผลลัพธ์ในที่สุด

ตัวอย่าง

#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; 
}

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

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