ডিভিজরদের যোগফল, মানে আজকের লেখার আমরা দেখব একটি সংখ্যা n এর সবগুলো ডিভিজরের যোগফল কীভাবে বের করতে হবে।
যেমন, 12 এর ডিভিজরদের যোগফল 1 + 2 + 3 + 4 + 6 + 12 = 28।
এটি আমরা n এর বর্গমূল পর্যন্ত লুপ চালিয়ে খুব সহজেই বের করে ফেলতে পারি। কিন্তু, আমরা আজকে দেখব কীভাবে
প্রাইম ফ্যাক্টরাইজেশন দিয়ে এটি বের করা যায় আরো কম সময়ে। আগের লেখা
ডিভিজর এবং সবগুলো ডিভিজর তে দেখেছি কীভাবে প্রাইম ফ্যাক্টরাইজ করে ডিভিজর সংখ্যা এবং আরো একটু মডিফাই অর্থাৎ ব্যাকট্র্যাকিং যুক্ত করে কীভাবে সবগুলো ডিভিজর বের করতে হয়। সেই প্রোগ্রাম টিই আরো একটু মডিফাই করলেই আমরা ডিভিজরদের যোগফল পেতে পারি। মানে একটি ডিভিজর পেয়ে আমরা সেই ডিভিজর টি একটি অ্যারেতে স্টোর করে রাখতাম বা, প্রিন্ট করে দিতাম। কিন্তু, আমরা এই প্রোগ্রামে সেটি না করে সেই ডিভিজর টি একটি ভেরিয়েবলে যোগ করে রাখলেই পেয়ে যাচ্ছি সবগুলো ডিভিজরের যোগফল। আপনি যদি আগের লেখাটি পড়ে থাকেন তাহলে এই কাজটি এখন আপনার জন্য সহজ। এরপরেও আমি কোড দিয়ে দিচ্ছি। তবে, আশাকরছি কোড দেখার আগেই আপনি নিজেই কোড টি লিখে ফেলতে পারবেন।
|
vector <pair <int, int> > prime;
int SOD;
// function to find all divisors using backtrack
void find_sum_of_all(int id, int cur) {
if (id == prime.size()) {
SOD += cur;
return;
}
for (int i = 0;i <= prime[id].second;i++) {
find_sum_of_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++;
}
prime.push_back({p[i], power});
}
}
if (n > 1)prime.push_back({n, 1});
SOD = 0;
find_sum_of_all(0, 1);
// now print sum of divisors
cout << SOD << '\n';
}
|
এখন একটি প্রশ্ন, ডিভিজরদের যোগফল পাওয়ার জন্য কি ব্যাকট্র্যাকিং লাগবেই? আমাদের ত শুধু দরকার যোগফল। আচ্ছা,
আগের লেখায় মোট ডিভিজর কীভাবে পেয়েছিলাম সেটি দেখতে পারি 12 এর জন্য। দেখা যাক সেখান থেকে কোন আইডিয়া পাওয়া যায় কিনা।
12 = 2 X 2 X 3
12 = 2^2 X 3^1
এখন, ডিভিজর গুলো আলাদা বের করে ফেলি রিকারসিভ ফাংশনের আদলে,
2^0 X 3^0 = 1
2^0 X 3^1 = 3
2^1 X 3^0 = 2
2^1 X 3^1 = 6
2^2 X 3^0 = 4
2^2 X 3^1 = 12
এখন, (1 + 3) = 4, (2 + 6) = 8 এবং (4 + 12) = 16 পেতে পারি আরো কম কাজ করেই,
2^0 X (3^0 + 3^1) = 4
2^1 X (3^0 + 3^1) = 8
2^2 X (3^0 + 3^1) = 16
আসলে আরো কাজ কমিয়ে সম্পূর্ণ যোগফল একেবারেই পেতে পারি,
(2^0 + 2^1 + 2^2) X (3^0 + 3^1) = 28
(1 + 2 + 4) X (1 + 3) = 28
7 X 4 = 28
এতক্ষণে হয়ত বুঝতে পেরেছেন আসলে
আগের লেখার NOD() ফাংশন টি একটু মডিফাই করলেই পেয়ে যাব মোট ডিভিজরদের যোগফল। NOD() ফাংশনে একটি প্রাইম ডিভিজর পেলে সেটি কতবার এসেছে তা কাউন্ট করে রেখে গুণ করে দিতাম এবার কতবার এসেছে তার প্রতিবারের জন্য যোগ করে রেখে সেটি গুণ করে দিব। মানে, 2 যদি দুইবার আসে তাহলে 2^0 + 2^1 + 2^2 বা, 1 + 2 + 4।
|
int SOD(int n) {
int ret = 1;
for (int i = 0;i < p.size() && p[i]*p[i] <= n;i++) {
if (n%p[i]==0) {
int sum = 1;
int power = 1;
while (n%p[i]==0) {
n /= p[i];
power *= p[i];
sum += power;
}
// sum is now p^0 + p^1 + p^2 ..............
ret *= sum;
}
}
if (n > 1) {
// if n is prime then 1 + n will multiply
ret *= (n+1);
}
return ret;
}
|
প্র্যাক্টিস প্রবলেমঃ
এই বিষয়ে আরো টিউটোরিয়াল।
No comments