链接
https://ac.nowcoder.com/acm/contest/8282/D
题意
$T$ 次询问,求 $\sum_{i=1}^n\sum_{j=1}^n\mu(ij)$ $(T,n\le 5e4)$
思路
$\begin{aligned}
& \sum_{i=1}^n\sum_{j=1}^n\mu(ij) \
= & \sum_{i=1}^n\sum_{j=1}^n\mu(ij)[\gcd(i,j)=1] \
= & \sum_{i=1}^n\sum_{j=1}^n\mu(ij)\sum_{d\mid\gcd(i,j)}\mu(d) \
= & \sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(id)\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\mu(jd) \
= & \sum_{d=1}^n\mu(d)(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(id))^2
\end{aligned}$
对于 $n\in[kd,(k+1)d)$,$(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(id))^2$ 相等。
预处理 $(\sum_{i=1}\mu(id))^2$ 时,将贡献差分,最后 $O(1)$ 询问。
预处理的时间复杂度为 $O(n\log(n))$。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| #include <bits/stdc++.h> #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(),(x).end() #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second using namespace std; typedef double DB; typedef long double LD; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<PII> VPII;
const int N=5e4+5; int mn[N],mu[N]; LL sum[N],res[N]; VI p; void get_mu(int n) { mu[1]=1; for(int i=2;i<=n;i++) { if(!mn[i]) mn[i]=i,mu[i]=-1,p.PB(i); for(auto x:p) { if(x*i>n) break; mn[x*i]=x; if(i%x==0) {mu[x*i]=0;break;} mu[x*i]=-mu[i]; } } } void init(int n) { for(int i=1;i<=n;i++) { for(int j=i;j<=n;j+=i) { sum[i]+=mu[j]; res[j]+=mu[i]*sum[i]*sum[i]; if(j+i<=n) res[j+i]-=mu[i]*sum[i]*sum[i]; } } for(int i=1;i<=n;i++) res[i]+=res[i-1]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); get_mu(5e4); init(5e4); int T;cin>>T; while(T--) { int n;cin>>n; cout<<res[n]<<'\n'; } return 0; }
|