दो संख्याएं start और end दी गई हैं जो धनात्मक पूर्णांकों की एक रेंज दर्शाती हैं। लक्ष्य उन सभी संख्याओं की गिनती ढूंढना है जो रेंज [start,end] में हैं और जिनका अभाज्य गुणनखंड ऐसा है कि उस संख्या के सभी अभाज्य गुणनखंडों की घातें ऐसी हैं कि उनका GCD 1 है।
यदि किसी संख्या का अभाज्य गुणनखंड 2p * 3q * 5r ….. है। तो घातें p,q,r ...का gcd=1 होना चाहिए।
उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - start = 1, end = 10
आउटपुट - रेंज में उन संख्याओं की गिनती जिनके अभाज्य गुणनखंडों की घातों का GCD 1 है: 6
व्याख्या - संख्याएं हैं:
2 ( 21 ), 3 ( 31 ), 5 ( 51 ), 7 ( 71 ), 8 ( 23 ) और 10 ( 21*51 )। प्रत्येक अभाज्य गुणनखंड की सभी घातों का gcd 1 है।
इनपुट - start = 11, end = 20
आउटपुट - रेंज में उन संख्याओं की गिनती जिनके अभाज्य गुणनखंडों की घातों का GCD 1 है: 9
व्याख्या - संख्याएं हैं:
11 ( 111 ), 12 ( 31*22 ), 13 ( 131 ), 14 ( 21*71 ), 15 ( 31*51 ), 17 ( 171 ), 18 ( 21*32 ), 19 ( 191 ) और 20 ( 22*51 )। प्रत्येक अभाज्य गुणनखंड की सभी घातों का gcd 1 है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम रेंज start से end तक उन सभी संख्याओं को गिनेंगे जो पूर्ण घात नहीं हैं। क्योंकि गैर-पूर्ण घात उपरोक्त शर्त को पूरा करेंगे। इसके लिए हम सभी पूर्ण घातें ढूंढेंगे और उन्हें कुल गिनती से हटा देंगे।
उत्तर होगा = start-end +1 - ( रेंज[start,end] में उन संख्याओं की गिनती जो पूर्ण घात हैं )।
- रेंज वेरिएबल start और end को इनपुट के रूप में लें।
- घात 3 से बड़ी संग्रहीत करने के लिए वेक्टर vec लें।
- पूर्ण वर्ग वाली संख्याओं को संग्रहीत करने के लिए सेट sett लें।
- गैर-पूर्ण वर्ग वाली संख्याओं को संग्रहीत करने के लिए सेट sett_2 लें।
- फ़ंक्शन calculate() वेक्टर vec और सेट sett और sett_2 को भरता है। पूर्ण वर्ग, गैर-पूर्ण वर्ग और घात>3 वाली संख्याओं को अलग करने के लिए।
- i=2 से i<size तक for लूप का उपयोग करके पार करें।
- sett में पूर्ण घात i*i डालें।
- IF sett.find(i) != sett.end()) true लौटाता है तो i एक पूर्ण वर्ग है और sett में मौजूद है तो कुछ न करें।
- वर्तमान संख्या की घात बड़ी से कम रहने तक while लूप चलाएं।
- विषम घातों को sett_2 में डालें क्योंकि सम घात पूर्ण वर्ग हैं और sett में हैं।
- अंत में for लूप का उपयोग करके sett_2 के क्रमबद्ध मानों को वेक्टर vec में डालें।
- फ़ंक्शन GCD_1(long int start, long int end) रेंज को इनपुट के रूप में लेता है और रेंज में उन संख्याओं की गिनती लौटाता है जिनके अभाज्य गुणनखंडों की घातों का GCD 1 है।
- calculate() कॉल करें।
- रेंज में पूर्ण वर्गों की गणना करें per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1)) के रूप में।
- upper_bound(vec.begin(), vec.end(), end) - vec.begin() का उपयोग करके vec में start का ऊपरी मान गणना करें।
- इसी तरह lower_bound(vec.begin(), vec.end(), start) - vec.begin() का उपयोग करके vec में end का निचला मान गणना करें।
- पूर्ण घातों की गणना करें 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
