gcd求和问题(莫比乌斯反演)

​​​​​​ P2522 [HAOI2011]Problem b P3455 [POI2007]ZAP-Queries 1、设 2、那么有 , 通过枚举 可以将式子 化简到 3、通过莫比乌斯反演,可以得到 ,将 化掉得到式子 4、令 , , 然后使用整除优化,询问时间复杂度 P3455 [POI2007]ZAP-Queries for (int i = 1; i < MAXN; i++) { mu[i] = (mu[i] + mu[i - 1]); phi[i] = (phi[i] + phi[i - 1]); } } int main() {