杜教筛求调

#include <bits/stdc++.h>
using namespace std;

#define int long long

int Sieve( int n , int p[] , int phi[] , int mu[] ) {
  int pcnt = 0;
  vector< int > vis( n + 5 );
  phi[ 1 ] = mu[ 1 ] = 1;
  vis[ 0 ] = vis[ 1 ] = 1;
  for( int i = 2 ; i <= n ; i++ ) {
    if( !vis[ i ] ) {
      p[ ++pcnt ] = i;
      phi[ i ] = i - 1;
      mu[ i ] = -1;
    }
    for( int j = 1 ; j <= pcnt && i * p[ j ] <= n ; j++ ) {
      vis[ i * p[ j ] ] = 1;
      if( i % p[ j ] == 0 ) {
        phi[ i * p[ j ] ] = phi[ i ] * p[ j ];
        break;
      }
      phi[ i * p[ j ] ] = phi[ i ] * phi[ p[ j ] ];
      mu[ i * p[ j ] ] = -mu[ i ];
    }
  }
  return pcnt;
}

const int _ = 1e6 + 5;

int p[_] , phi[_] , mu[_] , summu[_] , sumphi[_];

unordered_map< int , int > ansphi , ansmu;

int n;

int GetPhi( int x ) {
  if( x <= _ - 5 ) return sumphi[ x ];
  if( ansphi[ x ] ) return ansphi[ x ];
  int ans = ( x + 1 ) * x / 2;
  for( int l = 2 , r ; l <= n ; l = r + 1 ) {
    r = min( x , x / ( x / l ) );
    ans -= ( r - l + 1 ) * GetPhi( x / l );
  }
  return ansphi[ x ] = ans;
}

int GetMu( int x ) {
  if( x <= _ - 5 ) return summu[ x ];
  if( ansmu[ x ] ) return ansmu[ x ];
  int ans = 1;
  for( int l = 2 , r ; l <= x ; l = r + 1 ) {
    r = min( x , x / ( x / l ) );
    ans -= ( r - l + 1 ) * GetMu( x / l );
  }
  return ansmu[ x ] = ans;
}

void Solve() {
  cin >> n;
  cout << GetPhi( n ) << ' ' << GetMu( n ) << '\n';
}

signed main() {
  Sieve( _ - 5 , p , phi , mu );
  for( int i = 1 ; i <= _ - 5 ; i++ ) {
    summu[ i ] = summu[ i - 1 ] + mu[ i ];
    sumphi[ i ] = sumphi[ i - 1 ] + phi[ i ];
  }
  int tt = 1;
  cin >> tt;
  while( tt-- ) {
    Solve();
  }
}