Find the sum of divisors from 1 to n

ধরা যাক, আপনাকে একটা সংখ্যা 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 –
 4 – 2
 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