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

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

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

ให้เราเข้าใจด้วยตัวอย่าง

ตัวอย่าง

ป้อนข้อมูล - เริ่มต้น =1 สิ้นสุด =10

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

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

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

ป้อนข้อมูล - เริ่มต้น =11 สิ้นสุด =20

ผลลัพธ์ - การนับจำนวนในช่วงที่มี 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 +1 - ( นับจำนวนในช่วง[start,end] ที่เป็นกำลังสมบูรณ์ )

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

ตัวอย่าง

#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