题目大意 求 ∑ai=1∑bj=1∑ck=1[(i,j)=1][(i,k)=1][(j,k)=1]
推式子 首先假设a<=b<=c。
第一步转化为
∑ai=1∑bj=1,(j,i)=1∑ck=1,(k,i)=1[(j,k)=1]
注意到 [n=1]=∑d|nμ(d)
所以转化为
∑ai=1∑bj=1,(j,i)=1∑ck=1,(k,i)=1∑d|j,d|kμ(d)
交换一下枚举顺序
∑ai=1∑bd=1,(d,i)=1μ(d)?∑bj=1,(j,i)=1,d|j∑ck=1,(k,i)=1,d|k1
后面可以直接计算。
∑ai=1∑bd=1,(d,i)=1μ(d)?(∑bdj=1,(j,i)=11)?(∑cdk=1,(k,i)=11)
我们可以直接枚举i，然后考虑计算。
这个形式其实和一道叫循环之美的题差不多哦！
首先观察后两维可以分块。
于是我们需要计算一个和k互质的<=n的i的莫比乌斯函数和或者个数。
计算这个即可。
容易想到洲阁筛。
设S(i,r)表示<=r的与k的前i个质因子互质的莫比乌斯函数和。
S(i,r)=S(i?1,r)?μ(pi)?S(i,r/pi)
注意因为莫比乌斯函数要不含平方因子，所以后面那个第一维仍然是i，即要求它只有一个pi。
设T(i,r)表示<=r的与与k的前i个质因子互质的数的个数。
T(i,r)=T(i?1,r)?T(i?1,r/pi)
这样递归加记忆化有点慢。
我们考虑处理g[i]表示将i每个质因子的次数改成1的数。
一个优化是一开始枚举i的时候相同g的可以利用之前的答案。
于是我们只需要计算莫比乌斯函数不为0的i。
然后设f[i]表示i的最大质因数。
我们把S的意义改为<=r的与i互质的莫比乌斯函数和，T同理。
这样的好处是可以全局记忆化。
注意到状态只有n^1.5，可以开数组存。
为什么n^1.5？因为只有分块边界会进去，而不断除以一个质数的过程可以看做常数级别。
递归会比较慢，可以改为递推的形式提前计算。
详见代码。
#include
#include
#include
#include
推荐阅读
