আলোচনাঃ
আমাকে n দেয়া থাকবে, আমাকে n থেকে ছোট সব divisor এর যোগফল বের করতে হবে।
উত্তরঃ
20 = 1 x 20
= 2 x 10
= 4 x 5
—————————
= 5 x 4
= 10 x 2
= 20 x 1
আমরা জানি, কোনো সংখ্যার sqrt(n) পর্যন্ত check করলেই সে সংখ্যার সব divisor পাওয়া যায়। তো 20 এর প্রথম দুইটা divisor হচ্ছে 1 আর 20. তাহলে প্রথমেই আমরা n এর divisor হিসেবে n=20 পেয়ে যাচ্ছি। কিন্তু আমদের প্রশ্ন অনুযায়ী n থেকে ছোট সব divisor এর যোগফল বের করা লাগবে। তাই 20 কে বাদ দেয়া লাগবে। আর এর জন্য আমরা 2 থেকে divisor গুলোর sum নিতে পারি। কিন্তু তাহলে divisor হিসেবে 1 বাদ যায়। তাই sum এর শেষে / শুরুতে 1 যোগ করে দিলেই হলো।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
if(n==1) printf("0\n");
/*
A proper divisor of a natural number is
the divisor that is strictly less than the
number. There is 0 which is less than
1.So, sum = 0 .
*/
else{
ll sum=1;
for(int i=2;i*i<=n;i++){ // O(sqrt(n))
if(n%i==0){
if(i==n/i) sum+=i;
else sum+=i+(n/i);
}
}
printf("%d\n",sum);
}
}
}