題解
首先把題目轉化為求
\[\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]\]
大力杜教篩即可。
代碼