In this problem it's easy to get TLE while using general approach. here you have to follow one rule which is

       1. The total number of divisors of a number is just doubled of divisors till the square root of that number though there's some special case which is if the square root of given number is an integer then the total number of divisors is 2*number of divisors till sqrt(number) -1 otherwise 2*number of divisors till sqrt(number).

for example let a given number is 6 then sqrt(6) = 2.4494 . here 1 and 2 (2 divisors till sqrt(6)) is the divisors till 2.4494(sqrt(6)) and the square root is not an integer(2.4494) so total number of divisors is 2*2=4.

again, let a given number is 25 then sqrt(25) = 5 . here 1 and 5 (2 divisors till sqrt(25)) is the divisors till 5(sqrt(25)) and the square root is an integer(5) so total number of divisors is 2*2-1=3.
similarly you will have to find each number's total number of divisors. then output the number which has largest divisors.

an accepted code is given below:

Solution in c++:


  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5. long long t,a,b,r,j,c,i,temp,value,mx;
  6. cin>>t;
  7. while(t--)
  8. {
  9. mx=0;
  10. cin>>a>>b;
  11. for(i=a; i<=b; i++)
  12. {
  13. c=0;
  14. for(j=1;j<=sqrt(i); j++)
  15. {
  16. if(i%j==0)
  17. {
  18. c++;
  19. }
  20. }
  21. int temp=sqrt(i);
  22. if(temp==sqrt(i))
  23. {
  24. c=2*c-1;
  25. }
  26. else
  27. {
  28. c=2*c;
  29. }
  30. if(c>mx)
  31. {
  32. mx=c;
  33. value=i;
  34. }
  35. }
  36. printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n",a,b,value,mx);
  37. }
  38. }



No comments

Most View Post

Recent post

Codeforces Round 971 (Div. 4) 2009C. The Legend of Freya the Frog Solution

  Problem Link    https://codeforces.com/contest/2009/problem/C S olution in C++: /// Author : AH_Tonmoy #include < bits / stdc ++. h ...

Powered by Blogger.