首页 > 代码库 > 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