【BZOJ 4173】数学(数论)

Description

给定$n,m$,求

$$\phi(n)\times \phi(m)\times \sum_{k|n\% k+m\% k\geq k}\phi(k)\space mod \space 998244353$$

$n,m\leq 10^{15}$

题目解析

哇,此乃神题也,去年不会看了题解,今年还是不会看了题解。

首先我们分析$k$的性质,因为$(n+m)\% k < k\leq n\% k+m\% k$。

就有$n%k$和$m%k$的再次组成了一个$k$。

于是$\lfloor\frac{n+m}{k}\rfloor-\lfloor\frac{n}{k}\rfloor-\lfloor\frac{m}{k}\rfloor=1$

那么原式就可以转化为:

$$\phi(n)\times \phi(m)\times (\sum_{k=1}^{n+m}\phi(k)\times\lfloor\frac{n+m}{k}\rfloor-\sum_{k=1}^{n}\phi(k)\times\lfloor\frac{n}{k}\rfloor-\sum_{k=1}^{m}\phi(k)\times\lfloor\frac{m}{k}\rfloor)$$

又因为

$$\sum_{k=1}^{n}\phi(k)\times\lfloor\frac{n}{k}\rfloor =\sum_{i=1}^{n}\sum_{d|i}\phi(d)=\sum_{i=1}^{n}i$$

所以最后的答案:

$$Ans=\phi(n)\times\phi(m)\times n\times m$$

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注