题解：P4152 [WC2014] 时空穿梭

我们考虑枚举每一条直线，一条线可以用两个点来表示。假设我们定一个向量 $\vec{x}=(x_1,x_2,x_3……,x_n)$ ，那么第一个点可以取 $\prod_{i=1}^n(m_i-x_i)$ 种，令 $d=\gcd(x_1,x_2……)$ ，那么这条线上只有 $d$ 个整点。可以得式子：

然后就是推了。

莫反得 $[\gcd(t_1,t_2……)=1]=\sum_{k|t_1,k|t_2……k|t_n}\mu(k)$ 。

记 $f(T,c)=\sum_{d|T}\binom{d-1}{c-2}\mu(\frac{T}{d}),g(n,T)=\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}\prod_{i=1}^n(m_i-Tt_i)$

$f(T,c)$ 是好算的，我们重点看 $g(n,T)$

$\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}(m_n-Tt_n)$ 不就是一个等差数列求和吗？

这是不是可以看作一个 $T$ 的且系数只和 $\lfloor \frac{m_i}{T} \rfloor, m_i$ 有关的多项式，令 $xh_i$ 代表多项式的系数。

带回原式。

因为系数只和 $\lfloor \frac{m_i}{T} \rfloor, m_i$ 有关，所以一个整除分块来对系数预处理即可。

完结撒花\o/