问题

给定,求

解法

一些想法

这个题目是偶然做一道数论题时YY出来的,原题是三维的,要求复杂度,我降了一维,事实上,这是原题的部分解题步骤。

相似的题目

曾经POI07年有过一道类似的题目:求

这个题目就是直接利用莫比乌斯函数进行容斥解决,具体来说:

总复杂度

这个题目

那么仍然由上面的推导过程,写出答案的表达式

考虑枚举,需要求。似曾相识的式子?还记得经典的Eraosthenes的质数筛法吗?有一个常用的证明复杂度的公式:

用到上面的式子里来,每次直接暴力枚举的倍数,分别算关于的答案再相乘(这是一个类似卷积的东西),可以保证复杂度为