[ABC162E] Sum of gcd of Tuples (Hard)

标签：lfloor ... frac gcd Sum Hard rfloor Tuples sum

题面翻译

给定\(n,k\)，求

\[\sum^k_{a_1=1}\sum^k_{a_2=1}\sum^k_{a_3=1}\dots\sum^k_{a_n=1}gcd(a_1,a_2,a_3,\dots,a_n)\ mod\ 1000000007 \]

制約

• $ 2\ \leq\ N\ \leq\ 10^5 $
• $ 1\ \leq\ K\ \leq\ 10^5 $。

思路点拨

我们看到这么多 \(\gcd\) 的式子，我们自然想到莫比乌斯反演。

\[\sum_{d=1}^k d \sum_{a_1=1}^k \sum_{a_2=1}^k ... \sum_{a_n=1}^k [\gcd(a_1,a_2,...,a_n)=d] \]

\[\sum_{d=1}^k d \sum_{a_1=1}^{\lfloor \frac{k}{d}\rfloor} \sum_{a_2=1}^{\lfloor \frac{k}{d}\rfloor} ... \sum_{a_n=1}^{\lfloor \frac{k}{d}\rfloor} [\gcd(a_1,a_2,...,a_n)=1] \]

\[\sum_{i=1}^k d \sum_{t=1}^{\lfloor \frac{k}{d}\rfloor} \mu(t) (\lfloor \dfrac{k}{dk}\rfloor)^n \]

蛮力算就是 \(O(n \log n \log n)\) 。

标签：lfloor,...,frac,gcd,Sum,Hard,rfloor,Tuples,sum
From： https://www.cnblogs.com/Diavolo/p/17483782.html