题意 : 求 \(\sum_{i=1}^{n}{\sum_{j=1}^{i}{\sum_{k=1}^{i}{gcd(i,j,k)}}} \space mod \space p\); 其中\(n,p \leq 10^9\)
下式均在\(mod \space p\)意义下进行。
由\(\phi*1=id\)得到\(\sum_{i=1}^{n}{\sum_{j=1}^{i}{\sum_{k=1}^{i}{gcd(i,j,k)}}}\)
\(=\sum_{i=1}^{n}{\sum_{j=1}^{i}{\sum_{k=1}^{i}{\sum_{d|gcd(i,j,k)}{\phi(d)}}}}\)
\(=\sum_{d=1}^{n}{\phi(d)\sum_{d|i}^{n}{\sum_{d|j}^{i}{\sum_{d|k}^{i}{1}}}}\)
\(=\sum_{d=1}^{n}{\phi(d){\sum_{i=xd}^n{\sum_{j=yd}^i{\sum_{k=zd}^i}1}}}\)
\(=\sum_{d=1}^{n}{\phi(d){\sum_{i=1}^{\lfloor{n/d}\rfloor} {\sum_{j=1}^{i}{\sum_{k=1}^{i}}1}}}\)
设\(S(n)=\sum_{i=1}^n{i^2}\) 且\(S(n)=\frac{n(n+1)(2n+1)}{6}\)
那么有 \(\sum_{d=1}^{n}{\phi(d){\sum_{i=1}^{\lfloor{n/d}\rfloor} {i^2}}}\)
\(=\sum_{d=1}^n{\phi(d)S(\lfloor{\frac{n}{d}}\rfloor)}\)
满足杜教筛形式。
原文：https://www.cnblogs.com/cjc030205/p/11638084.html