「TFOI R1」Average Number 题解

· · 题解

Solution

这里是验题人题解。

因为平均值为 \dfrac{\left(\displaystyle\sum_{i=1}^{n}i \right)-m}{n-1}=a+\dfrac{b}{c}，所以 c \mid n-1，设 n=c\cdot i+1。

注意到出题人给的样例中算出的 i 很小，我们可以大胆猜测出题人的数据中算出的 i 也会很小，考虑暴力枚举 i。

以下是这项思路的具体代码实现。

for(long long i=1,n,m;;++i){
    n=c*i+1;
    m=(__int128)n*(n+1)/2-(__int128)a*(n-1)-b*i;
    if(m>=1&&m<=n){
        printf("%lld %lld\n",n,m);
        break;
    }
}

但是，这样的复杂度肯定是错的，期望得分为 15 pts。

其实在我重造数据之前，对于随机数据这种做法跑得飞快，因为 i 此时多数情况下等于 1。

时间浪费在了枚举了很多无用的值，导致算出的 m 不在正确的范围 1 \sim n 之间。

所以考虑求解不等式来缩小 i 的范围。

下面来推一波式子。

\begin{aligned} &\because 0<\dfrac{(c\cdot i+1)(c\cdot i+2)}{2}-a\cdot c\cdot i-b\cdot i \le c\cdot i+1 \\\\ &\therefore 0<(c\cdot i+1)(c\cdot i+2)-(2\cdot a\cdot c+2\cdot b)\cdot i \le 2\cdot c\cdot i+2 \\\\ &\therefore 0<c^2\cdot i^2+(3\cdot c-2\cdot a\cdot c-2\cdot b)\cdot i + 2 \le 2\cdot c\cdot i+2 \\\\ &\therefore \begin{cases} c^2\cdot i^2+(3\cdot c-2\cdot a\cdot c-2\cdot b)\cdot i + 2 > 0 \\\\ c^2\cdot i^2+(c-2\cdot a\cdot c-2\cdot b)\cdot i \le 0 \end{cases} \\\\ &\because i>0 \\\\ &\therefore \begin{cases} i > \dfrac{-(3\cdot c-2\cdot a\cdot c-2\cdot b)+\sqrt{(3\cdot c-2\cdot a\cdot c-2\cdot b)^2-8\cdot c^2}}{2\cdot c^2} \\\\ i \le -\dfrac{c-2\cdot a\cdot c-2\cdot b}{c^2} \end{cases} \end{aligned}

当然第一个不等式可能无解，此时不用管它。

这样，i 的枚举时间复杂度为 O(1)。

上述做法可以通过本题，不过如此冗长的式子令人望而生畏。

下面提供我冥思苦想后得到的第二种做法，十分简易。

\begin{aligned} &a+\dfrac{b}{c}=\dfrac{n(n+1)-2m}{2(n-1)}=\dfrac{n}{2}+\dfrac{n-m}{n-1} \\ &\therefore \begin{cases} a\le \dfrac{n}{2}+\dfrac{n-m}{n-1}\Longrightarrow a-1\le \dfrac{n}{2} \\\\ a+\dfrac{b}{c}\ge\dfrac{n}{2}\Longrightarrow a+1\ge \dfrac{n}{2} \end{cases} \\ &\therefore2a-2\le n \le 2a+2 \end{aligned}

于是可以直接 O(1) 求出合法的 n,m。

至此，本题得到了合理的解决。