Description

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

6

1

2

8

13

30

2333

Sample Output

1 1

2 0

22 -2

58 -3

278 -3

1655470 2

Solution

杜教筛裸题啊

对于 \(\mu\) ，利用与它有关的卷积 \(\mu*1=e\) ，杜教筛式子为 \(S(n)=1-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\)

对于 \(\varphi\) ，利用与它有关的卷积 \(\varphi*1=id\) ，杜教筛式子为 \(S(n)=\sum_{i=1}^ni-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\)

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst int MAXN=3000000+10;int t,n,vis[MAXN],prime[MAXN],cnt,phi[MAXN],mu[MAXN],smu[MAXN];ll sphi[MAXN];std::map
     
       M;std::map
      
        P;namespace IO{    const ui Buffsize=1<<15,Output=1<<23;    static char Ch[Buffsize],*S=Ch,*T=Ch;    inline char getc()    {        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);    }    static char Out[Output],*nowps=Out;    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}    template
       
        inline void read(T&x)    {        x=0;static char ch;T f=1;        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);        x*=f;    }    template
        
         inline void write(T x,char ch='\n')    {        if(!x)*nowps++='0';        if(x<0)*nowps++='-',x=-x;        static ui sta[111],tp;        for(tp=0;x;x/=10)sta[++tp]=x%10;        for(;tp;*nowps++=sta[tp--]^48);        *nowps++=ch;    }}using namespace IO;template
         
           inline void chkmin(T &x,T y){x=(y
          
           
             inline void chkmax(T &x,T y){x=(y>x?y:x);}template
            
              inline T min(T x,T y){return x
             
              
                inline T max(T x,T y){return x>y?x:y;}inline void init(){ memset(vis,1,sizeof(vis)); vis[0]=vis[1]=0; phi[1]=mu[1]=1; for(register int i=2;i
               
                x)break; ll j=x/(x/i); res+=(j-i+1)*Smu(x/i); i=j+1; } return M[x]=1-res;}inline ll Sphi(ll x){ if(x
                
                 x)break; ll j=x/(x/i); res+=1ll*(j-i+1)*Sphi(x/i); i=j+1; } return P[x]=1ll*(x+1)*x/2-res;}int main(){ init();read(t); while(t--)read(n),write(Sphi(n),' '),write(Smu(n),'\n'); flush(); return 0;}