fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <chrono>
  3. #define  mx 100000001
  4. #define  ll   long long
  5. #define  pii pair<int, int>
  6. #define  debug printf("%d\n", bug++);
  7. #define  For(i,n) for(int i = 0; i < n; ++i)
  8. #define  INF 1 << 30
  9. #define  mod  1000000007
  10. using  namespace std;
  11. using  namespace std::chrono;
  12. int bug =120;
  13. int prime[mx];
  14. vector<int>primes;
  15. void seive() {
  16.     prime[1] = 0;
  17.     prime[2] = 1;
  18.     For(i, mx) prime[i] = 1;
  19.     for (int i = 4; i <= mx; i += 2) prime[i] = 0;
  20.     for (int i = 3; i * i < mx; i += 2) {
  21.         if (prime[i]) {
  22.             for (int j = i * i; j < mx; j += i) {
  23.                 prime[j] = 0;
  24.             }
  25.         }
  26.     }
  27.     for (int i = 2; i < mx; ++i)
  28.         if (prime[i])
  29.             primes.push_back(i);
  30. }
  31. ll cal(ll n) {
  32.     ll sum = 1;
  33.     ll tmp = -n;
  34.     int i = 0;
  35.     int cnt = 0;
  36.     while (primes[i] <= sqrt(n)) {
  37.         if (n % primes[i] == 0) {
  38.             cnt = 0;
  39.             while (n % primes[i] == 0) {
  40.                 cnt++;
  41.                 n /= primes[i];
  42.             }
  43.             double  x = pow(primes[i] , cnt + 1) - 1;
  44.             x /= (primes[i] - 1);
  45.             sum *= (ll int)(x);
  46.         }
  47.         i++;
  48.     }
  49.     if(n > 2){
  50.         double  x = pow(n ,2 ) -1;
  51.         x /= (n -1);
  52.         sum *= (ll int)(x);
  53.     }
  54.     return  sum + tmp;
  55. }
  56. int main(){
  57.     int t;
  58.     scanf("%d" ,&t);
  59.     seive();
  60.     For(tc, t){
  61.         ll a;
  62.         scanf("%lld", &a);
  63.         if(a == 1){
  64.             printf("0\n");
  65.             continue;
  66.         }
  67.         else if(a == 2){
  68.             printf("1\n");
  69.             continue;
  70.         }
  71.         printf("%lld\n",cal(a));
  72.  
  73.     }
  74.  
  75. }
  76.  
Success #stdin #stdout 1.9s 426824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CkjPGm
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!