题目大意：

　　$q(q\leq50)$组询问，对于给定的$n(n\leq10^7)$，求$\displaystyle\sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^n[\gcd(i,j,k)=1]$。

思路：

　　$原式=\sum_{d=1}^n(\lfloor\frac{n}{d}\rfloor^3+3\lfloor\frac{n}{d}\rfloor^2+3\lfloor\frac{n}{d}\rfloor)\mu(d)$。数论分块即可。

1 #include
     
       2 #include
      
        3 typedef long long int64; 4 inline int getint() { 5     register char ch; 6     while(!isdigit(ch=getchar())); 7     register int x=ch^'0'; 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9     return x;10 }11 const int N=10000001,M=664580;12 bool vis[N];13 int mu[N],sum[N],p[M];14 inline void sieve() {15     mu[1]=1;16     for(register int i=2;i
      
     

 

原式=\sum_{d=1}^n(\lfloor\frac{n}{d}\rfloor^3+3\lfloor\frac{n}{d}\rfloor^2+3\lfloor\frac{n}{d}\rfloor)\mu(d)$。数论分块即可。