考虑把 d(xy) 这个玩意拆开。
发现 d(xy)=∑i|x∑j|y[gcd(i,j)=1]。
然鹅并不会证明……这里传送到 Siyuan 的证明。
于是题目就是问的 n∑i=1m∑j=1∑x|i∑y|j[gcd(x,y)=1]。
对于上面式子,我们可以转化一下思路:枚举 x,y,计算其对给定范围内所有数的贡献。
于是有
n∑i=1m∑j=1∑x|i∑y|j[gcd(x,y)=1]=n∑i=1m∑j=1⌊ni⌋⌊mj⌋[gcd(i,j)=1]
然后设 f(x)=n∑i=1m∑j=1⌊ni⌋⌊mj⌋[gcd(i,j)=x],F(x)=∑x|if(i)=n∑i=1m∑j=1⌊ni⌋⌊mj⌋[x|gcd(i,j)]。
n∑i=1m∑j=1⌊ni⌋⌊mj⌋[x|gcd(i,j)]=∑xi≤n∑xj≤m⌊nxi⌋⌊mxj⌋
那么有 f(x)=∑x|iμ(ix)F(i),此题求 f(1)=n∑i=1μ(i)F(i)=n∑i=1μ(i)∑xi≤n⌊⌊nx⌋i⌋∑yi≤m⌊⌊my⌋i⌋。
对于任意的 n,预处理一下 n∑i=1⌊ni⌋ 和 μ 的前缀和然后数论分块。
代码:
1 |
|