[hdu6715]算术

首先要知道一个式子：$\mu(lcm(i,j))=\mu(i)\cdot \mu(j)\cdot \mu(gcd(i,j))$（分是否为0讨论）
令$d=gcd(i,j)$，$n'=\lfloor n/d \rfloor$，$m'=\lfloor m/d \rfloor$
$\sum \mu(lcm(i,j))$
$=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n'}\mu(id) \sum_{j=1}^{m'}\mu(jd)\sum_{g|i,g|j}\mu(g)$
令$n''=\lfloor n'/g \rfloor$，$m''=\lfloor m'/g \rfloor$
$=\sum_{d=1}^{n}\mu(d)\sum_{g=1}^{n'}\mu(g)\sum_{i=1}^{n''}\mu(igd) \sum_{j=1}^{m''}\mu(jgd)$
令$t=gd$
$=\sum_{t=1}^{n}\mu*\mu(t)\sum_{i=1}^{n''}\mu(it) \sum_{j=1}^{m''}\mu(jt)$
其中$\mu*\mu$和后半部分都是可以预处理的，预处理复杂度$o(nlnn)$，询问暴力枚举t，复杂度$o(Tn)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 1000005

 4 int t,n,m,mu[N],vis[N],p[N],mu2[N];

 5 vector<int>mu3[N];

 6 long long ans;

 7 int gcd(int x,int y){

 8     if (!y)return x;

 9     return gcd(y,x%y);

10 }

11 int main(){

12     mu[1]=1;

13     for(int i=2;i<N-4;i++){

14         if (!vis[i]){

15             p[++p[0]]=i;

16             mu[i]=-1;

17         }

18         for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){

19             vis[i*p[j]]=1;

20             if (i%p[j]==0){

21                 mu[i*p[j]]=0;

22                 break;

23             }

24             mu[i*p[j]]=-mu[i];

25         }

26     }

27     for(int i=1;i<N-4;i++)

28         for(int j=1;j<=(N-5)/i;j++)mu2[i*j]+=mu[i]*mu[j];

29     for(int i=1;i<N-4;i++){

30         mu3[i].push_back(mu[i]);

31         for(int j=2;j<=(N-5)/i;j++)mu3[i].push_back(mu3[i][j-2]+mu[i*j]);

32     }

33     scanf("%d",&t);

34     while (t--){

35         scanf("%d%d",&n,&m);

36         ans=0;

37         if (n>m)swap(n,m);

38         for(int i=1;i<=n;i++)ans+=1LL*mu2[i]*mu3[i][n/i-1]*mu3[i][m/i-1];

39         printf("%lld\n",ans);

40     }

41 }

巴特西

[hdu6715]算术

最新文章

热门文章