ডিভিজর সংখ্যা এবং সবগুলো ডিভিজর(Number of Divisors and Find All)
আমরা প্রাইম ফ্যাক্টরাইজেশন দিয়ে N এর প্রাইম ডিভিজর গুলো বের করেছিলাম। এই অ্যালগরিদম থেকেই মোট ডিভিজর বের করাও খুব সহজ, শুধু একটু মডিফাই করতে হবে। সেটি কীভাবে? যদি একটি সংখ্যার প্রাইম ডিভিজর গুলো দেখি,
12 = 2 X 2 X 3
12 = 2^2 X 3^1
এখন পাওয়ার গুলোর সাথে যদি 1 যোগ করে তাদের গুণ করি, তাহলে গুণফল ই হচ্ছে 12 এর মোট ডিভিজর সংখ্যা। NOD(); হচ্ছে একটি ফাংশন যেটি আমাদের ডিভিজর সংখ্যা বের করে দিবে।
NOD(12) = (2+1) X (1+1)
NOD(12) = 6
12 এর মোট ডিভিজর হচ্ছে 6 টি, 1 2 3 4 6 12। অন্য আরেকটি সংখ্যা 90 এর যদি জন্য দেখি তাহলে,
90 = 2 X 3 X 3 X 5
90 = 2^1 X 3^2 X 5^1
NOD(90) = (1+1) X (2+1) X (1+1)
NOD(90) = 12
90 এর মোট ডিভিজর হচ্ছে 12 টি, 1 2 3 5 6 9 10 15 18 30 45 90।
যদি প্রাইম ফ্যাক্টরাইজেশন ভালো করে শিখে থাকেন তাহলে হয়ত এতক্ষণে বুঝে গেছেন কি করতে হবে :) আর যদি না বুঝে থাকেন তাহলে নিচের কোড দেখার আগে একটু সময় নিয়ে ভেবে দেখুন, হয়ত নিজে নিজেই কোড করে ফেলতে পারবেন।
|
int NOD(int n) { int ret = 1, power;
for (int i = 0;i < p.size() && p[i]*p[i] <= n;i++) { if (n%p[i] == 0) { power = 0;
// now count total power of current prime while (n%p[i] == 0) { n /= p[i]; power++; }
power += 1; ret *= power; } }
if (n > 1) { power = 2; ret *= power; }
return ret; } |
এখানে p অ্যারেটি তে প্রাইম নাম্বার রেখেছি ম্যাক্সিমাম ইনপুট লিমিটের বর্গমূল পর্যন্ত। শুধু কোন প্রাইম নাম্বার কতবার এসেছে তা কাউন্ট করে গুণ করে রেখে দিচ্ছি। এটিই হচ্ছে প্রাইম ফ্যাক্টরাইজেশন এর সাথে NOD() ফাংশনের এর পার্থক্য।
আমরা N এর কয়টি ডিভিজর আছে তা বের করতে পারলাম কিন্তু প্রাইম ফ্যাক্টরাইজ করে কি ডিভিজর গুলো পাওয়া সম্ভব? অবশ্যই সম্ভব তবে একটু ব্যাকট্র্যাকিং এর সাহায্য নিতে হবে।
আচ্ছা, উপরে আমি শুধু N এর ডিভিজর সংখ্যা বের করব কীভাবে তার অ্যালগরিদম ও কোড দিয়েছি কিন্তু প্রাইম এর হাইয়েস্ট পাওয়ার গুলোর সাথে 1 যোগ করে গুণ করলেই কেন মোট ডিভিজর সংখ্যা বের হয়ে যাচ্ছে তা নিয়ে কিন্তু কিছু বলিনি। এখন সেটি দেখব কারণ N এর সবগুলো ডিভিজর পেতে হলে আমাদের কারণ জানাটাও প্রয়োজন। নিচে 90 এর জন্য দেখতে পারি নিয়ম টি।
90 = 2^1 X 3^2 X 5^1
এখন, প্রতিটি প্রাইম এর জন্য সর্বোচ্চ পাওয়ার পর্যন্ত সবগুলো লিখি,
2^1 পর্যন্ত, 2^0 2^1
1 2
3^2 পর্যন্ত, 3^0 3^1 3^2
1 3 9
5^1 পর্যন্ত, 5^0 5^1
1 5
এখন, {1 2}, {1 3 9} এবং {1 5} এই তিনটি গ্রুপ থেকে একটি করে সংখ্যা নিয়ে কতটি ভিন্ন কম্বিনেশন করতে পারব?
1 X 1 X 1 = 1 1 X 1 X 5 = 5
1 X 3 X 1 = 3 1 X 3 X 5 = 15
1 X 9 X 1 = 9 1 X 9 X 5 = 45
2 X 1 X 1 = 2 2 X 1 X 5 = 10
2 X 3 X 1 = 6 2 X 3 X 5 = 30
2 X 9 X 1 = 18 2 X 9 X 5 = 90
1 5 3 15 9 45 2 10 6 30 18 90
তাহলে সহজেই বলা যায় প্রাইম গুলোর হাইয়েস্ট পাওয়ারের সাথে 1 যোগ করে তাদের গুণ করে দিলেই পেয়ে যাব মোট ডিভিজর।
90 = 2^1 X 3^2 X 5^1
NOD(90) = (1+1) X (2+1) X (1+1)
NOD(90) = 12
এখন তাহলে কোড করার পালা। এবার একটি paired অ্যারে ব্যবহার করব, প্রথমে রাখব প্রাইম ডিভিজর টি এবং দ্বিতীয়তে রাখব হাইয়েস্ট পাওয়ার। এই কাজটি করব একটি ফাংশনে এবং ডিভিজর বের করার কাজটি করব আরেকটি রিকারসিব ফাংশনে।
|
// array to store every prime divisor up to it's highest power vector <pair <int, int> > prime;
// function to find all divisors using backtrack void find_all(int id, int cur) { if (id == prime.size()) { cout << cur << ' '; return; }
for (int i = 0;i <= prime[id].second;i++) { find_all(id+1, cur);
cur *= prime[id].first; } }
// function to store every prime divisor up to it's highest power void find_prime_div(int n) { for (int i = 0;i < p.size() && p[i]*p[i] <= n;i++) { if (n%p[i] == 0) { int power = 0;
while (n%p[i] == 0) { n /= p[i]; power++; } // storing prime divisor and it's highest power prime.push_back({p[i], power}); } } // storing prime divisor and it's highest power if (n > 1)prime.push_back({n, 1});
find_all(0, 1); } |
রিকারসিভ ফাংশন টি ভালো করে উপলব্ধি এবং পুরো বিষয়টি ভালো করে বুঝার জন্য নিচের ছবিটি আশাকরি একটু হেল্প করবে।
 |
| 90 = 2^1 X 3^2 X 5^1 |
প্র্যাক্টিস প্রবলেমঃ
Number of Common Divisors
এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১
টিউটোরিয়াল ২
টিউটোরিয়াল ৩
টিউটোরিয়াল ৪
টিউটোরিয়াল ৫
No comments