Advertisement
momo2345

Untitled

Jun 1st, 2021
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  4. #define ll long long
  5. #define pb push_back
  6. #define endl "\n"
  7. const int mx = 1e8+123;
  8. bitset<mx> is_prime;
  9. vector<int> prime;
  10.  
  11. void primegen ( int n )
  12. {
  13. n += 100;
  14. for ( int i = 3; i <= n; i += 2 ) is_prime[i] = 1;
  15.  
  16. int sq = sqrt ( n );
  17. for ( int i = 3; i <= sq; i += 2 ) {
  18. if ( is_prime[i] == 1 ) {
  19. for ( int j = i*i; j <= n; j += ( i + i ) ) {
  20. is_prime[j] = 0;
  21. }
  22. }
  23. }
  24.  
  25. is_prime[2] = 1;
  26. prime.push_back (2);
  27.  
  28. for ( int i = 3; i <= n; i += 2 ) {
  29. if ( is_prime[i] == 1 ) prime.push_back ( i );
  30. }
  31. }
  32. ll SOD(ll l)
  33. {
  34. ll ret=1;
  35. for(auto p: prime)
  36. {
  37. if(1LL*p*p >l) break;
  38. ll currSum=1;
  39. ll powP=1;
  40. if(l%p==0)
  41. {
  42. while(l%p==0)
  43. {
  44. powP*=p;
  45. currSum+=powP;
  46. l/=p;
  47. }
  48. }
  49. ret*=currSum;
  50. }
  51. if(l>1) ret*=(l+1);
  52. return ret;
  53. }
  54. int main()
  55. {
  56. suni;
  57. primegen(1e3);
  58. int t; cin>>t;
  59. while(t--){
  60. int n;
  61. cin>>n;
  62. cout<<SOD(n)-n<<endl;}
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement