Spoj DIVSUM2 - Divisor Summation (Hard) Solution

 

Problem Link : https://www.spoj.com/problems/DIVSUM2/

Algorithm Link : https://cp-algorithms.com/algebra/divisors.html

Solution in C++: 

1. ///La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. ///Abul Hasnat Tonmoy
4. ///Department of CSE,23rd batch
5. ///Islamic University,Bangladesh
6. #include <bits/stdc++.h>
7. using namespace std;
8. #define mx 100000009
9. #define ll long long
10. bitset<mx>isprime;
11. vector<ll>prime;
12. void sieve()
13. {
14. isprime.set();
15. isprime[0]=false;
16. isprime[1]=false;
17. for(int i=0; i<mx; i++)
18. {
19. if(isprime[i])
20. {
21. prime.push_back(i);
22. for(int j=i*2; j<mx; j+=i)
23. isprime[j]=false;
24. }
25. }
26. }
27. ll power(ll p,ll q)
28. {
29. if(q==0)
30. return 1;
31. if(q==1)
32. return p;
33. ll ans=1;
34. while(q--)
35. ans*=p;
36. return ans;
37. }
38. ll solution(ll n)
39. {
40. ll sum=1,cnt;
41. for(int i=0; i<prime.size()&&i*i<n; i++)
42. {
43. if(n%prime[i]==0)
44. {
45. cnt=0;
46. while(n%prime[i]==0)
47. {
48. cnt++;
49. n/=prime[i];
50. }
51. sum*=(power(prime[i],cnt+1)-1)/(prime[i]-1);
52. }
53. }
54. if(n>1)
55. {
56. sum*=n+1;/// for prime number
57. }
58. return sum;
59. }
60. int main()
61. {
62. long long n,a,b,count,i,p,t,cn,sum;
63. sieve();
64. cin>>t;
65. while(t--)
66. {
67. cin>>n;
68. cout<<solution(n)-n<<endl;
69. }
70. }