【莫比乌斯反演】HDU6428 Problem C. Calculate

###题意：
求$$\sum _{i=1}^{i\le A}\sum _{j=1}^{j\le B}\sum _{k=1}^{k\le C}\phi (gcd(i,j^2,k^3))$$

###分析：
膜拜cch。。。
狄利克雷卷积：$(f?g)(D)={\sum }_{d|D}f(d)\times g(\frac{D}{d})$
由狄利克雷卷积的性质，可得
$$e=1?\mu$$(e表示单位元)
$$\phi =\phi ?e=\phi ?\mu ?1$$(单位元卷任意函数等于其本身，且狄利克雷卷积具有交换律)
由此可得，原式=$$\sum _{i=1}^{i\le A}\sum _{j=1}^{j\le B}\sum _{k=1}^{k\le C}\sum _{d|i,d|j^2,d|k^3}(\phi ?\mu )(d)$$

$$=\sum _{d=1}^{d\le A}(\phi ?\mu )(d)\sum _{i=1}^{i\le A}\sum _{j=1}^{j\le B}\sum _{k=1}^{k\le C}[d|i且d|j^2且d|k^3]$$

将x唯一分解，设为$x=\prod p_i^{k_i}$，如果$x|y^t$那么$\prod p_i^{?\frac{k_i}{t}?}|y$
设$f_t(x)=\prod p_i^{?\frac{k_i}{t}?}$

那么原式就可以进一步化为
$$=\sum _{d=1}^{d\le A}(\phi ?\mu )(d)?\frac{A}{f_1(d)}??\frac{B}{f_2(d)}??\frac{C}{f_3(d)}?$$

(其实$f_1(x)=x$)
$(\phi ?\mu )$肯定是积性函数，我就不解释了。。。
然后$f_t(x)$也可以通过欧拉筛的性质（被最小的质因数筛到），来线性地筛出来

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 10000010
#define MAXP 10000000
#define MOD 1000000007
using namespace std;
int n;
int f[MAXN],f2[MAXN],f3[MAXN],ti[MAXN],las[MAXN];
bool isprime[MAXN];
int primes[MAXN],tot;
void prepare(){f[1]=1;f2[1]=1;f3[1]=1;for(int i=2;i<=MAXP;i++){if(isprime[i]==0){primes[++tot]=i;f[i]=i-2;las[i]=1;ti[i]=1;f2[i]=i;f3[i]=i;}for(int j=1;1ll*primes[j]*i<=1ll*MAXP;j++){isprime[i*primes[j]]=1;if(i%primes[j]==0){las[i*primes[j]]=las[i];int x=las[i];int p=primes[j];int px=i*primes[j]/las[i];f[i*primes[j]]=(px-2*px/p+px/p/p)*f[x];ti[i*primes[j]]=ti[i]+1;f2[i*primes[j]]=f2[i];if(ti[i]%2==0)f2[i*primes[j]]*=primes[j];f3[i*primes[j]]=f3[i];if(ti[i]%3==0)f3[i*primes[j]]*=primes[j];break;}las[i*primes[j]]=i;ti[i*primes[j]]=1;f[i*primes[j]]=f[i]*f[primes[j]];f2[i*primes[j]]=f2[i]*f2[primes[j]];f3[i*primes[j]]=f3[i]*f3[primes[j]];}}
}
int main(){prepare();SF("%d",&n);int A,B,C;while(n--){SF("%d%d%d",&A,&B,&C);int ans=0;for(int i=1;i<=A;i++)ans+=f[i]*(A/i)*(B/f2[i])*(C/f3[i]);PF("%d\n",ans&((1<<30)-1));}
}