C++ এ 1 এর সমান মৌলিক গুণনীয়কের ক্ষমতার GCD সহ একটি পরিসরে সংখ্যা গণনা করুন

ধনাত্মক পূর্ণসংখ্যার একটি সীমার প্রতিনিধিত্বকারী দুটি সংখ্যা শুরু এবং শেষ দেওয়া হয়েছে। লক্ষ্য হল পরিসরে থাকা সমস্ত সংখ্যার গণনা খুঁজে বের করা [শুরু, শেষ] এবং মৌলিক ফ্যাক্টরাইজেশন রয়েছে যাতে সেই সংখ্যার সমস্ত মৌলিক গুণনীয়কগুলির ক্ষমতা থাকে যেমন তাদের 1 হিসাবে GCD থাকে৷

যদি একটি সংখ্যার 2 ^p হিসাবে প্রাইম ফ্যাক্টরাইজেশন থাকে * 3 ^q * 5 ^r ….. তারপর পাওয়ার p,q,r ...এর gcd=1 থাকা উচিত।

আসুন উদাহরণ দিয়ে বোঝা যাক।

উদাহরণস্বরূপ

ইনপুট - start =1, end =10

আউটপুট - 1-এর সমান মৌলিক গুণনীয়কগুলির GCD শক্তি বিশিষ্ট একটি পরিসরে সংখ্যার সংখ্যা হল:6

ব্যাখ্যা - সংখ্যাগুলো হল:

2 ( 2 ¹ ), 3 ( 3 ¹ ), 5 ( 5 ¹ ), 7 ( 7 ¹ ), 8 ( 2 ³ ) এবং 10 ( 2 ¹ *5 ¹ ) প্রতিটি প্রাইম ফ্যাক্টরাইজেশনের সমস্ত শক্তির 1 হিসাবে gcd থাকে।

ইনপুট - start =11, end =20

আউটপুট - 1-এর সমান মৌলিক গুণনীয়কগুলির GCD শক্তি বিশিষ্ট একটি পরিসরে সংখ্যার সংখ্যা হল:9

ব্যাখ্যা - সংখ্যাগুলো হল:

11 ( 11 ¹ ), 12 ( 3 ¹ *2 ² ), 13 ( 13 ¹ ), 14 ( 2 ¹ *7 ¹ ), 15 ( 3 ¹ *5 ¹ ), 17 ( 17 ¹ ), 18 ( 2 ¹ *3 ² ), 19 ( 19 ¹ ) এবং 20 ( 2 ² *5 ¹ ) প্রতিটি প্রাইম ফ্যাক্টরাইজেশনের সমস্ত শক্তির 1 হিসাবে gcd থাকে।

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ

এই পদ্ধতিতে আমরা পরিসীমার শুরু থেকে শেষ পর্যন্ত সমস্ত সংখ্যা গণনা করব যা নিখুঁত শক্তি নয়। যেহেতু অ-নিখুঁত ক্ষমতা উপরের শর্ত পূরণ করবে। এর জন্য আমরা সমস্ত নিখুঁত ক্ষমতা খুঁজে পাব এবং তাদের মোট গণনা থেকে সরিয়ে দেব।

উত্তর হবে =শুরু-শেষ +1 - ( পরিসরে সংখ্যার গণনা [শুরু, শেষ] যা নিখুঁত শক্তি)।

• রেঞ্জ ভেরিয়েবলের শুরু এবং শেষ ইনপুট হিসাবে নিন।
• 3-এর বেশি শক্তি সঞ্চয় করতে ভেক্টর vec নিন।
• নিখুঁত বর্গাকার সংখ্যা সঞ্চয় করতে একটি সেট সেট নিন।
• নিখুঁত বর্গ নয় এমন সংখ্যা সংরক্ষণ করতে একটি সেট sett_2 নিন।
• ফাংশন calculate() ভেক্টর vec এবং সেট সেট এবং sett_2 সেট করে। নিখুঁত বর্গ, অ-নিখুঁত বর্গ এবং শক্তি>3।
সংখ্যাগুলিকে আলাদা করতে
• i=2 থেকে i
• নিখুঁত ক্ষমতা সন্নিবেশ করান i*i সেট করতে।
• যদি sett.find(i) !=sett.end()) সত্য হয় তাহলে আমি একটি নিখুঁত বর্গক্ষেত্র এবং সেটে উপস্থিত তাই কিছুই করবেন না।
• লুপ চলাকালীন চালান যতক্ষণ না বর্তমান সংখ্যার শক্তি বড় থেকে কম থাকে।
• সেট_2-এ বিজোড় শক্তি সন্নিবেশ করান কারণ জোড় শক্তিগুলি নিখুঁত বর্গক্ষেত্র এবং সেটে৷
• শেষে লুপ ব্যবহার করে ভেক্টর vec-তে sett_2 এর সাজানো মান সন্নিবেশ করান।
• ফাংশন GCD_1(লং int স্টার্ট, লং int এন্ড) ইনপুট হিসাবে পরিসর নেয় এবং 1 এর সমান প্রাইম ফ্যাক্টরের ক্ষমতার GCD সহ একটি ব্যাপ্তিতে সংখ্যার গণনা প্রদান করে।
• কল ক্যালকুলেট().
• প্রতি_sq =floor(sqrtl(end)) - floor(sqrtl(start - 1)) হিসাবে পরিসরে নিখুঁত বর্গক্ষেত্র গণনা করুন।
• upper_bound(vec.begin(), vec.end(), end) - vec.begin() ব্যবহার করে vec-তে শুরুর উপরের মান গণনা করুন।
• ঠিক =low_bound(vec.begin(), vec.end(), start) - vec.begin() ব্যবহার করে একইভাবে vec-তে শেষের নিম্ন মান।
• 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