UOJ#221. 【NOI2016】循环之美 数论,杜教筛

题解

首先把题目转化为求

\[\sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y) = 1] [ \gcd(y,k) = 1]\]

推式子：

\[\sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y) = 1] [ \gcd(y,k) = 1]\\ = \sum_{i = 1}^{\min(n,m)} \mu(i) \sum_{x=1}^{\left \lfloor \frac n i \right \rfloor } \sum_{y=1}^{\left \lfloor \frac m i \right \rfloor } [\gcd(iy,k) = 1]\\ = \sum_{i = 1}^{\min(n,m)}\left \lfloor \frac n i \right \rfloor \mu(i) [\gcd(i,k) = 1] \sum_{y=1}^{\left \lfloor \frac m i \right \rfloor } [\gcd(y,k) = 1]\]

整除分块一下，变成求

\[\sum_{i = 1} ^ n \mu(i) [\gcd(i,k) = 1] \]

\[\sum_{i = 1} ^ n \mu(i) [\gcd(i,k) = 1] \\ = \sum_{i = 1} ^ n \mu(i) - \sum_{i = 1} ^ n \mu(i) [\gcd(i,k) > 1] \\ = \sum_{i = 1} ^ n\mu(i) - \sum_{d>1,d|k} \sum_{i = 1} ^ {\lfloor \frac n d \rfloor} [\gcd(id,k) = d] \mu(id)\]

其中

\[[\gcd(id,k) = d] \mu(id) \\ = [\gcd(id,k) = d] \mu(i) \mu(d) [\gcd(i,d) = 1] \\ = \mu(d) [\gcd(i,k) = 1] \mu(i) \]

所以，原式 =

\[\sum_{i = 1} ^ n\mu(i) - \sum_{d>1,d|k} \mu(d) \sum_{i = 1} ^ {\lfloor \frac n d \rfloor} \mu(i) [\gcd(i,k) = 1]\]

大力杜教筛即可。

代码