ধরা
যাক,
আপনাকে একটা সংখ্যা n দিয়ে বললো
1 থেকে n পর্যন্ত সংখ্যাগুলোর
divisor(1 এবং সেই সংখ্যা বাদে) গুলোর যোগফল
বের করতে।
যেমনঃ
6 এর divisor গুলো হচ্ছে 2, 3। যোগফল
হচ্ছে
5।
এখন
n এর মান যদি 6 হয় তাহলে উত্তর হবে
0+0+0+2+0+5 = 7।
যেহেতু 1, 2, 3, 4, 5 ,6 সংখ্যাগুলোর divisor গুলোর যোগফল যথাক্রমে
0, 0, 0, 2, 0, 5।
O(n) solution:
এই
প্রবলেমটার সবচেয়ে সহজ সমাধান হচ্ছে 1 থেকে
n পর্যন্ত একটা for লুপ চালিয়ে প্রত্যেকটি
i এর জন্য (floor(n / i) – 1) * i বের করে
যোগ করা।
এইখানে floor(n/i) এর মাধ্যমে বের করা হচ্ছে 1 থেকে n পর্যন্ত কতগুলো সংখ্যা i দিয়ে
divisible.
যেমনঃ
6/2 = 3, এর মানে হচ্ছে 1 থেকে 6
পর্যন্ত 3 টি সংখ্যা (2, 4, 6) 2
দিয়ে divisible.
আর
floor(n/i)
থেকে 1 বিয়োগ করা হচ্ছে কারণ
divisor হিসেবে নিজেকে নেয়া যাবে না। অর্থাৎ
এখানে
6 এর divisor হচ্ছে শুধু 2 এবং 3।
O(n/2) solution:
উপরের
সলুশনের ক্ষেত্রে আসলে n/2 পর্যন্ত ফর লুপ চালালেই
আমরা সলুশন পেয়ে যাব কারণ n/2+1 থেকে n পর্যন্ত সংখ্যা গুলো নিজেদের ছাড়া 1 থেকে
n পর্যন্ত অন্য কোন সংখ্যার-ই
divisor না।
O(sqrt(n)) solution:
আমরা
আগেই দেখেছি, যদি floor(n/i) = x হয় এর মানে হচ্ছে 1 থেকে n পর্যন্ত নিজেকে ছাড়া x-1 টি সংখ্যা i দ্বারা divisible. উল্টাটাও কিন্তু সত্য,
মানে হচ্ছে 1 থেকে n পর্যন্ত নিজেকে ছাড়া i-1 টি সংখ্যা x দ্বারা divisible.
ধরা
যাক,
n = 30।
1 থেকে 30 পর্যন্তু সংখ্যাগুলোর
divisor (1 এবং নিজেকে বাদে) গুলো নিচে দেয়া
হলঃ
1 –
2 –
3 –
5 –
6 – 2, 3
7 –
8 – 2, 4
9 – 3
10 – 2, 5
11 --
12 – 2, 3, 4, 6
13 --
14 – 2, 7
15 – 3, 5
16 – 2, 4, 8
17 --
18 – 2, 3, 6, 9
19 --
20 – 2, 4, 5, 10
21 – 3, 7
22 – 2, 11
23 --
24 – 2, 4, 6, 12
25 -- 5
26 – 2, 13
27 – 3, 9
28 – 2, 4, 7, 14
29 --
30 – 2, 3, 5, 6, 10, 15
floor(30/2) = 15, অর্থাৎ 1 থেকে 30 পর্যন্ত
2 টি সংখ্যা 15 দ্বারা
divisible, নিজেকে বাদ দিলে 1 শুধু একটি
সংখ্যা(20) 15 দ্বারা divisible।
আবার
floor(30/3) = 10, অর্থাৎ 1 থেকে
30 পর্যন্ত নিজেকে বাদে 2 টি সংখ্যা
(20, 30) 10 দ্বারা divisible।
এখন
একটূ খেয়াল করলে দেখা যাবে যে, floor(30/3)+1 = 11 থেকে floor(30/2) = 15 পর্যন্ত 5 টি সংখ্যার (11, 12, 13, 14, 15) প্রত্যেকটি
1 থেকে 30 পর্যন্ত 2 টি সংখ্যার divisible।
একইভাবে
floor(30/4)+1
= 8 থেকে floor(30/3) = 10 পর্যন্ত 3
টি সংখ্যার (8, 9, 10) প্রত্যেকটি
1 থেকে 30 পর্যন্ত 3 টি সংখ্যার divisible।
অর্থাৎ,
floor(n/i) + 1 থেকে floor(n/(i+1)) পর্যন্ত
সংখ্যাগুলোর প্রত্যেকটি 1 থেকে n পর্যন্ত i টি সংখ্যার divisible।
তাহলে,
আমরা আসলে 1 থেকে sqrt(n) পর্যন্ত ফর লুপ চালালেই সলুশন পেয়ে যাচ্ছি।
Code:
for(i=2; i <= sqrt(n); i++) {
ans = ((n/i) - 1) * i;
temp = n / i;
if(temp > i) {
a = n / (i+1);
b = n / i;
sum1 = (a * (a+1)) / 2;
sum2 = (b * (b+1)) / 2;
ans += (sum2 - sum1) * (i - 1);
}
}
এই
ব্লগটা খুবই তাড়াহুড়ো করে লিখা, তাই ঠিকমত সবকিছু
গুছায়ে বলা হয় নাই।
তাছাড়া এইটাই আমার ফার্স্ট ব্লগ,
তাই পড়ে কিছু না বুজলে আমার কিছু করার নাই :p । আর যদি বুজতে পারলে আলোর
(lightoj.com) 1098 নাম্বার প্রবলেমটা সল্ভ করা যেতে পারে,
কোড তো দিয়াই দিলাম :p ।
তবে
আশা করি,
সামনে আরো সুন্দর করে সময় নিয়ে নিয়মিত ব্লগ লিখব :D
