DIVSUM

در online judge problems

سلام برو بچ

خب قراره یکی از سوالات سایت Spoj رو اینجا دور همی حل کنیم و این سوال هم اسمش اسم همین مطلب هست یعنی سوال DIVSUM

خب اول صورت سوال که برای راحتی از سایت اصلی اینجا کپی پیست کردم ولی خب آخرش که باید خودتون هم برید تو سایت اصلی و سوال رو سامبیت کنید ،بگذریم ،بهتره که بریم سر اصل مطلب یعنی صورت سوال

 

74. Divisor Summation

Problem code: DIVSUM

Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Example

Sample Input:
3
2
10
20

Sample Output:
1
8
22

 

صورت سوال که هلوئه و هیچ ابهامی نداره تنها چیزی که از ما می خواد اینه که یه سری عدد (تقریباْ دویست هزار تا :دی) رو از ورودی بگیریم و مجموع مقسوم علیه های اونو محاسبه کنیم راه حلی که همون اول ممکنه به ذهنمون برسه اینه که دقیقاً مثل همون چیزی که تو سوال گفته عمل کنیم یعنی بخش پذیری عدد مورد نظر رو به همه اعداد کوچکتر از اون  چک کنیم و اگه دیدیم که بله این عدد به فلان عدد کوچکتر از خودش بخش پذیره این عدد کوچیکتره رو به عنوان یکی از مقسوم علیه های عدد مورد نظر در نظر بگیریم و به یک مجموع خاص اضافه اش کنیم اصن به جای اینکه این همه حرف الکی بزنم سریع کدش رو با سی پلاس پلاس بزنیم بهتره

 

  1. #include <iostream>
  2.  
  3. using namespace std;
  4. typedef unsigned long long Int64;
  5.  
  6. void solve(Int64 n){
  7. Int64 sum=0;
  8. for(Int64 i=1;i<n;i++){
  9.  
  10. if(n%i==0){
  11. sum=sum+i;
  12. }
  13. }
  14. cout<<sum<<"\n";
  15. }
  16. int main(){
  17. int c;
  18. Int64 num;
  19. cin>>c;
  20. for(int i=0;i<c;i++){
  21. cin>>num;
  22. solve(num);
  23. }
  24. return 0;
  25. }

خب این کد که خیلی نیاز به توضیح نداره اول داخل main تعداد تست کیس ها رو می گیریم و میریزیم توی c بعد یه حلقه اجرا میشه که به تعداد تست کیس ها از ورودی یه عددی رو می گیره و تابع solve رو فراخوانی می کنه

تابع solve هم ساده است یه حلقه از ۱ تا یه عدد قبل از عدد اصلی یعنی n اجرا میشه و به ازای هر i ای که n به اون بخش پذیر باشه یعنی n%i==0  درست باشه اونوقت i رو به sum که در ابتدا صفر هست اضافه می کنیم

و این یعنی دقیقاً همون چیزی که تو سوال گفته

ولی خب این راه حل به وضوح به TLE ختم میشه چراش هم ساده است چون تقریباً دویست هزار تا عدد تو ورودی میده تابع solve ای هم که نوشتیم از مرتبه O(N)d هست که N همون عددیه که از ورودی می خونیم N هم می تونه حد اکثر پونصد هزار باشه پس در بد ترین حالت تقریباً 200000*500000 تا محاسبه خواهیم داشت و این یعنی خیلی ، اصلاً از خیلی هم خیلی تر :دی

شک دارید کد زیر رو تو سیستم خودتون اجرا کنید

 

  1. #include <iostream>
  2. #include <time.h>
  3. using namespace std;
  4. typedef unsigned long long Int64;
  5.  
  6. int main(){
  7. Int64 a=5000000;
  8. Int64 b=2000000;
  9. Int64 ab=a*b;
  10.  
  11. time_t start,end;
  12.  
  13. time(&start);
  14.  
  15. for(Int64 i=0;i<ab;i++){
  16.  
  17. }
  18.  
  19. time(&end);
  20.  
  21. cout<<difftime(end,start)<<"\n";
  22.  
  23. return 0;
  24. }

تازه توی این کد داخل حلقه هیچ اتفاقی نمی افته و انقدر طول می کشه

پس باید بریم دنبال یه روش سریع تر

خب می دونیم که اگه یه عددی اول نباشه اونوقت حتماً عاملی کوچکتر مساوی رادیکال خودش داره یعنی هر وقت که بتونیم عدد m رو به صورت m=pq  بنویسیم اونوقت حتماً یا p یا q یکیشون باید از رادیکال m کوچیکتر باشه(کوچیکتر مساوی باشه ، منتهی چون سختمه که هی بنویسم کوچکتر مساوی از اینجا تا آخر این متن هر جا گفتم کوچکتر از رادیکال منظورم کوچکتر مساوی رادیکال هست اینو دیگه یادتون بمونه) اگه توضیحات بیشتر می خواهید برید لینک زیر رو یه نگاه بهش بندازید

اعداد اول-بخش یک

خب حالا که اینو می دونیم پس کافیه به جای اینکه حلقه داخل solve تا یه عدد قبل از n بره تا قبل از رادیکالش بره یعنی داخل solve اینجوری بشه

 

  1. void solve(Int64 n){
  2. Int64 sum=0;
  3. Int64 sq=sqrt(n);
  4. for(Int64 i=1;i<=sq;i++){
  5.  
  6. }
  7. cout<<sum<<"\n";
  8. }

ولی خب این حلقه هنوز داخلش خالیه و کار خاصی انجام نمی ده

خب وقتی بشه نوشت n=pq یعنی n به p و q بخش پذیر باشه اونوقت می دونیم که یکیش از رادیکال n کوچیکتره بدون اینکه هیچ شبه ای به وجود بیاد فرض کنیم این p هست که از رادیکال n کوچیکتره اونوقت q رو می تونیم به صورت زیر محاسبه کنیم

q=n/p

خود p رو هم که دیگه بلدیم چی جوری به دست بیاریم دیگه؟ هر عدد کوچکتر از رادیکال n که n به اون بخش پذیر باشه رو p در نظر می گیریم البته به جز عدد یک ، یعنی این دفعه حلقه رو از دو شروع می کنیم

پس کد قبل رو به صورت زیر توسعه می دیم

 

  1. void solve(Int64 n){
  2. Int64 sum=1;
  3. Int64 sq=sqrt(n);
  4. Int64 p,q;
  5.  
  6. for(Int64 i=2;i<=sq;i++){
  7. if(n%i==0){
  8. p=i;
  9. q=n/p;
  10. sum=sum+p+q;
  11. }
  12.  
  13. }
  14.  
  15. cout<<sum<<"\n";
  16. }

منتهی این کد یه جاش اشکال داره ، می دونید کجاش؟ خب فرض کنید که ورودی عدد ۲۵ باشه اونوقت یه بار i میشه ۲ که هیچ

یه بار میشه سه باز هم هیچ چون ۲۵ به ۳ پخش پذیر نیست

یه بار میشه چهار باز هم هیچ

و سر آخر میشه ۵ اینجا ۲۵ به ۵ بخش پذیره پس p باید بشه ۵ ولی q هم میشه ۵ اونوقت sum میشه پنج به علاوه پنج به علاوه ۱ یعنی ۱۱

کجای کار می لنگید؟

تنها مقسوم علیه های کوچکتر از ۲۵ اعداد ۵ و ۱ هستن پس جواب باید می شد ۶ نه یازده ، کجا اشتباه شد؟ بله ساده است ۵ اشتباهاً دو بار اضافه شده به مجموعه یعنی وقتی p=q باشه فقط باید یکی رو به sum اضافه کنیم که کار تکراری نکرده باشیم پس کد قبل رو به صورت زیر اصلاح می کنیم

 

 

  1. void solve(Int64 n){
  2. Int64 sum=1;
  3. Int64 sq=sqrt(n);
  4. Int64 p,q;
  5.  
  6. for(Int64 i=2;i<=sq;i++){
  7. if(n%i==0){
  8. p=i;
  9. q=n/p;
  10. if(p==q){
  11. sum=sum+p;
  12. }else{
  13. sum=sum+p+q;
  14. }
  15. }
  16.  
  17. }
  18.  
  19. cout<<sum<<"\n";
  20. }

فکر می کنید همه چی تموم شده؟ نه اشتباه می کنید، اگه تو ورودی عدد یک رو بدن چی؟ اونوقت اولش sum میشه یک و بعد نوبت به حلقه می رسه که اصلاً اجرا نمی شه در نتیجه جواب میشه یک که غلطه چون یک هیچ مقسوم علیه کوچکتر از خودش نداره پس جواب اصلی باید صفر باشه در نتیجه کد قبل رو یه بار دیگه هم اصلاح می کنیم

 

  1. void solve(Int64 n){
  2. Int64 sum=1;
  3. Int64 sq=sqrt(n);
  4. Int64 p,q;
  5.  
  6. for(Int64 i=2;i<=sq;i++){
  7. if(n%i==0){
  8. p=i;
  9. q=n/p;
  10. if(p==q){
  11. sum=sum+p;
  12. }else{
  13. sum=sum+p+q;
  14. }
  15. }
  16.  
  17. }
  18. if(n==1){
  19. sum=0;
  20. }
  21.  
  22. cout<<sum<<"\n";
  23. }

پس کد کاملمون به صورت زیر میشه

 

  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5. typedef unsigned long long Int64;
  6.  
  7. void solve(Int64 n){
  8. Int64 sum=1;
  9. Int64 sq=sqrt(n);
  10. Int64 p,q;
  11.  
  12. for(Int64 i=2;i<=sq;i++){
  13. if(n%i==0){
  14. p=i;
  15. q=n/p;
  16. if(p==q){
  17. sum=sum+p;
  18. }else{
  19. sum=sum+p+q;
  20. }
  21. }
  22.  
  23. }
  24. if(n==1){
  25. sum=0;
  26. }
  27.  
  28. cout<<sum<<"\n";
  29. }
  30. int main(){
  31. int c;
  32. Int64 num;
  33. cin>>c;
  34.  
  35. for(int i=0;i<<c;i++){
  36.  
  37. cin>>num;
  38. solve(num);
  39.  
  40. }
  41. return 0;
  42. }

خب این کد همه چیزش خوبه ولی برید یه بار حتماً سابمیتش کنید تو سایت اسپاج تا به یه چیز با حال بر بخورید

سابمیت کردید؟ TLE خوردید؟ چرا؟

چون cin و cout کند هستند و بهتره که از scanf و printf استفاده کنیم

راستی چون نوع داده ای که تعریف کردیم unsigned long long هست موقع خوندن از ورودی و نوشتن تو خروجی با استفاده از scanf و printf باید از %llu استفاده کنیم

یعنی سر آخر باید کدمون به صورت زیر باشه

 

  1. #include <iostream>
  2. #include <cmath>
  3. #include <stdio.h>
  4. using namespace std;
  5. typedef unsigned long long Int64;
  6.  
  7. void solve(Int64 n){
  8. Int64 sum=1;
  9. Int64 sq=sqrt(n);
  10. Int64 p,q;
  11.  
  12. for(Int64 i=2;i<=sq;i++){
  13. if(n%i==0){
  14. p=i;
  15. q=n/p;
  16. if(p==q){
  17. sum=sum+p;
  18. }else{
  19. sum=sum+p+q;
  20. }
  21. }
  22.  
  23. }
  24. if(n==1){
  25. sum=0;
  26. }
  27.  
  28. printf("%llu\n",sum);
  29. }
  30. int main(){
  31. int c;
  32. Int64 num;
  33. scanf("%d",&c);
  34.  
  35. for(int i=0;i<c;i++){
  36.  
  37. scanf("%llu",&num);
  38. solve(num);
  39.  
  40. }
  41. return 0;
  42. }

و اما نکات پایانی

یک با اینکه دیدیم cin و cout به نسبت کند هستن و بهتره از scanf و printf استفاده کنیم ولی خب این دو تا هم چندان مالی نیستن و ورودی و خروجی رو میشه خیلی سریع تر کرد یعنی حتی scanf و printf هم خیلی سریع نیستن که بعداً یه بحث ورودی خروجی حتماً به صورت یه پست جدا خواهیم داشت

دو اینکه حالا تا اینجاش اومدید ببینید زورتون به سوال زیر هم می رسه اگه آره چرا ؟ اگه نه چرا؟

DIVSUM2