首页 > 代码库 > BZOJ 2694: Lcm

BZOJ 2694: Lcm

Description

定义整数\(a,b\),求满足下列条件的\([a,b]\)的和.

\(1\leqslant a\leqslant A,1\leqslant b\leqslant B,\forall n>1,n^2\nmid (a,b),T\leqslant 2\times 10^4,A,B\leqslant 4\times 10^6\)

Solution

数论.

最后一个限制跟\(\mu\)有点关系,可以吧\(\mu\)平方一下..

这个题实质上就是求

\(\sum_{i=1}^n\sum_{j=1}^m\mu((i,j))^2[i,j]\)

\(=\sum_{i=1}^n\sum_{j=1}^m\mu((i,j))^2\frac{ij}{(i,j)}\)

\(=\sum_{d}\mu(d)^2\sum_{i=1}^n\sum_{j=1}^m[(i,j)=d]\frac{ij}{d}\)

\(=\sum_{d}\mu(d)^2d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[(i,j)=1]ij\)

\(=\sum_{d}\mu(d)^2d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{p\mid i}[p\mid j]\mu(p)ij\)

\(=\sum_{d}\mu(d)^2d\sum_{p}\mu(p)p^2\sum_{i=1}^{\lfloor \frac{n}{pd} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{pd} \rfloor}ij\)

\(\text{Let T=pd}\)

\(=\sum_{T}\sum_{d\mid T}\mu(d)^2d\mu(\frac{T}{d})\frac{T}{d}^2\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{T} \rfloor}ij\)

\(=\sum_{T}\sum_{d\mid T}\mu(d)^2d\mu(\frac{T}{d})\frac{T}{d}^2(\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor}i)(\sum_{j=1}^{\lfloor \frac{m}{T} \rfloor}j)\)

后面的式子可以直接分块来求,主要是前面的函数的前缀和.

\(g(n)=\sum_{d\mid n}\mu(d)^2d\mu(\frac{n}{d})\frac{n}{d}^2\)

因为他是积性函数的狄利克雷卷积,所以他也是积性函数,而且因为\(\mu\)的存在,一个质数至多存在2个是才会有贡献.

那么线性筛的时候,如果最小质因子超过2次,那么就是0,否则可以直接将它出去,变成两个互质的数.

现在就是考虑\(p^k\)怎么算,因为\(k\)只会是\(1,2\),所以我们可以...人脑暴力...

\(g(p)=\mu(1)^2\mu(p)p^2+\mu(p)^2p\mu(1)=-p^2+p\)

\(g(p^2)=\mu(p)^2p\mu(p)p^2=-p^3\)

做完了...因为我一口气写完了所有公式,而且不是用的编辑器...所以可能有错...如果发现请留言qwq...

双倍经验 BZOJ 4659: Lcm

Code

/**************************************************************    Problem: 2694    User: BeiYu    Language: C++    Result: Accepted    Time:2096 ms    Memory:79424 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long ll;const int N = 4000500;const int p = 0x3fffffff; int T,n,m;int pr[N],cp,b[N],mu[N],g[N];int f[N]; void pre(int n) {    mu[1]=1,g[1]=1;    for(int i=2;i<=n;i++) {        if(!b[i]) pr[++cp]=i,mu[i]=-1,g[i]=(1-i)*i;        for(int j=1;j<=cp && i*pr[j]<=n;j++) {            b[i*pr[j]]=1;            if(i%pr[j]) {                mu[i*pr[j]]=-mu[i];                g[i*pr[j]]=g[i]*g[pr[j]];            } else {                if((i/pr[j])%pr[j]) g[i*pr[j]]=g[i/pr[j]]*(-pr[j]*pr[j]*pr[j]);                else g[i*pr[j]]=0;                break;            }        }    }    for(int i=1;i<=n;i++) g[i]+=g[i-1];//  for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) f[j]+=mu[i]*mu[i]*mu[j/i]*(j/i);//  for(int i=1;i<=n;i++) f[i]=f[i]*i;//  for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<endl;//  for(int i=1;i<=n;i++) cout<<g[i]<<" ";cout<<endl;} int S(int n) { return ((ll)n*(n+1)/2); } int main() {//  time_t tt=clock();    pre(4000000);//  cout<<(clock()-tt)/1000.0/1000.0<<endl;    for(scanf("%d",&T);T--;) {        scanf("%d%d",&n,&m);        if(n>m) swap(n,m);        int ans=0;        for(int i=1,j;i<=n;i=j+1) {            j=min(n/(n/i),m/(m/i));//          cout<<i<<" "<<j<<" "<<S(n/i)*S(m/i)*(g[j]-g[i-1])<<endl;            ans+=S(n/i)*S(m/i)*(g[j]-g[i-1]);        }printf("%d\n",ans&p);    }    return 0;}

  

BZOJ 2694: Lcm