Advertisement
momo2345

SOD

Jun 1st, 2021
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 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.  
  33. ll SOD (ll l)
  34. {
  35.     ll ret = 1;
  36.     for ( auto p : prime ) {
  37.         if ( 1LL * p * p > l ) break;
  38.  
  39.         if ( l % p == 0 ) {
  40.             ll powP = p;
  41.  
  42.             while ( l % p == 0 ) {
  43.                 powP *= p;
  44.                 l/= p;
  45.             }
  46.  
  47.             ret *= ( ( powP - 1 ) / ( p - 1 ) );
  48.         }
  49.     }
  50.  
  51.     if ( l > 1 ) {
  52.         ret *= ( l + 1 );
  53.     }
  54.  
  55.     return ret;
  56. }
  57.  
  58.  
  59. int main()
  60. {
  61.     suni;
  62.  
  63.     primegen(1e8);
  64.  
  65.     int t;
  66.     cin >> t;
  67.  
  68.     while ( t-- ) {
  69.        ll n;
  70.         cin >> n;
  71.         cout << SOD (n) - n << endl;
  72.     }
  73.  
  74.     return 0;
  75. }
  76.  
  77.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement