计算如下式子
如果只是两个数字乘积的约数个数，那么有公式： σ ( i j ) = ∑ a ∣ i ∑ b ∣ j [ ( a , b ) = 1 ] \sigma(ij)=\sum_{a|i} \sum_{b|j}[(a,b)=1] σ(ij)=a∣i∑b∣j∑[(a,b)=1] 当有三个数字的时候，我们同样大胆猜测然后打表验证，可以得到如下公式： σ ( i j k ) = Σ a ∣ i Σ b ∣ j Σ c ∣ k [ ( a , b ) = 1 ] [ ( a , c ) = 1 ] [ ( b , c ) = 1 ] \sigma(ijk)=\Sigma_{a|i} \Sigma_{b|j}\Sigma_{c|k}[(a,b)=1][(a,c)=1][(b,c)=1] σ(ijk)=Σa∣iΣb∣jΣc∣k[(a,b)=1][(a,c)=1][(b,c)=1] 那么本题就相当于计算 Σ i = 1 a Σ j = 1 b Σ k = 1 c Σ x ∣ i Σ y ∣ j Σ z ∣ k [ ( x , y ) = 1 ] [ ( x , z ) = 1 ] [ ( y , z ) = 1 ] \Sigma_{i=1}^{a}\Sigma_{j=1}^{b}\Sigma_{k=1}^{c}\ \Sigma_{x|i} \Sigma_{y|j}\Sigma_{z|k}[(x,y)=1][(x,z)=1][(y,z)=1] Σi=1aΣj=1bΣk=1c Σx∣iΣy∣jΣz∣k[(x,y)=1][(x,z)=1][(y,z)=1] 考虑交换求和次序，先枚举x、y和z，然后三个相互互质可以等价于其中两个互质，第三个数字与前两个数字的乘积互质，于是可以转化为如下式子： Σ x = 1 a Σ y = 1 b ⌊ a x ⌋ ⌊ b y ⌋ [ ( x , y ) = 1 ] Σ z = 1 c ⌊ c z ⌋ [ ( x y , z ) = 1 ] \Sigma_{x=1}^{a}\Sigma_{y=1}^{b}\ \lfloor\frac{a}{x}\rfloor\lfloor\frac{b}{y}\rfloor [(x,y)=1]\ \Sigma_{z=1}^{c}\ \lfloor\frac{c}{z}\rfloor[(xy,z)=1] Σx=1aΣy=1b ⌊xa⌋⌊yb⌋[(x,y)=1] Σz=1c ⌊zc⌋[(xy,z)=1] 我们令 f ( n , m ) = Σ i = 1 m ⌊ m i ⌋ [ ( n , i ) = 1 ] f(n,m)=\Sigma_{i=1}^{m}\ \lfloor\frac{m}{i}\rfloor[(n,i)=1] f(n,m)=Σi=1m ⌊im⌋[(n,i)=1],显然这个是可以反演的，反演之后有： f ( n , m ) = Σ d ∣ n m μ ( d ) Σ i = 1 ⌊ m / d ⌋ ⌊ ⌊ m d ⌋ i ⌋ f(n,m)=\Sigma_{d|n}^{m}\ \mu(d) \Sigma_{i=1}^{\lfloor m/d \rfloor}\lfloor \frac{\lfloor\frac{m}{d}\rfloor}{i}\rfloor f(n,m)=Σd∣nm μ(d)Σi=1⌊m/d⌋⌊i⌊dm⌋⌋ 令 g ( n ) = Σ i = 1 n ⌊ n i ⌋ g(n)= \Sigma_{i=1}^{n}\lfloor \frac{n}{i}\rfloor g(n)=Σi=1n⌊in⌋，这个可以用数论分块在 O ( N ) O(\sqrt{N}) O(N )的时间复杂度内求出来。
那么 f ( n , m ) = Σ d ∣ n m μ ( d ) g ( ⌊ m d ⌋ ) f(n,m)=\Sigma_{d|n}^{m}\ \mu(d)g(\lfloor\frac{m}{d}\rfloor) f(n,m)=Σd∣nm μ(d)g(⌊dm⌋)可以在 O ( M ) O(M) O(M)的时间复杂度内求出来。
进而对于所有的 f ( x y , z ) f(xy,z) f(xy,z)，我们可以在 O ( N 2 ) O(N^2) O(N2)的时间复杂度内预处理出来。
这样，最后的答案就是： Σ x = 1 a Σ y = 1 b ⌊ a x ⌋ ⌊ b y ⌋ [ ( x , y ) = 1 ] f ( x y , z ) \Sigma_{x=1}^{a}\Sigma_{y=1}^{b}\ \lfloor\frac{a}{x}\rfloor\lfloor\frac{b}{y}\rfloor [(x,y)=1]\ f(xy,z) Σx=1aΣy=1b ⌊xa⌋⌊yb⌋[(x,y)=1] f(xy,z) 直接枚举i和j，判断 g c d ( i , j ) gcd(i,j) gcd(i,j)即可。总的时间复杂度为 O ( N 2 log N ) O(N^2\log N) O(N2logN)。具体见代码。
