『题解』P6055

标签：lfloor frac gcd 题解 sum rfloor P6055

给出 \(N\)，求：

\[\sum _ {i = 1} ^ N \sum _ {j = 1} ^ N \sum _ {p = 1} ^ {\lfloor\frac{N}{j}\rfloor} \sum _ {q = 1} ^ {\lfloor\frac{N}{j}\rfloor} [\gcd(i, j) = 1][\gcd(p, q) = 1]. \]

考虑化简。存在一个性质，但是我当时推的时候忘记了。即：

\[\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N[\gcd(j,k)=i]=\sum_{i=1}^N\sum_{j=1}^{\lfloor\frac{N}{i}\rfloor}\sum_{k=1}^{\lfloor\frac{N}{i}\rfloor}[\gcd(j,k)=1]. \]

然后回到上式，可化简为：

\[\sum_{i=1}^N\sum_{p=1}^N\sum_{q=1}^N[\gcd(i,p,q)=1]. \]

卷积展开得：

\[\sum_{d=1}^N\mu(d){\lfloor\dfrac{N}{d}\rfloor}^3. \]

因为数据范围很大，所以用杜教筛 + 数论分块求解。

标签：lfloor,frac,gcd,题解,sum,rfloor,P6055
From： https://www.cnblogs.com/Chronologika/p/17703452.html