Warning: session_start(): open(/tmp/sess_82d5b7f30170c2a35590217cc30147d8, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
设 $f(a,b,c,n,t_{1},t_{2})=\sum_{i=0}^{n}i^{t_{1}}\lfloor\frac{ai+b}{c}\rfloor^{t_{2}}$，求解这一函数值的算法因类似于欧几里得算法而得名类欧几里得算法。为了方便，这里仅讨论 $6$ 个参数均为非负整数的情况。另外我们定义 $0^{0}=1$。现将该算法描述如下：
定义 $m=\lfloor\frac{an+b}{c}\rfloor$，$g_{t}(x)=(x+1)^{t}-x^{t}=\sum_{i=0}^{t-1}g_{ti}x^{i}$，$h_{t}(x)=\sum_{i=1}^{x}i^{t}=\sum_{i=0}^{t+1}h_{ti}x^{i}$。
首先描述几种特殊情况：
* 若 $t_{2}=0$，那么有：
$$
\begin{aligned}
原式&=\sum_{i=0}^{n}i^{t_{1}}\\
&=h_{t_{1}}(n)+[t_{1}=0]
\end{aligned}
$$
* 若 $m=0$，那么显然有：
$$
原式=0
$$
* 若 $a=0$，那么有：
$$
\begin{aligned}
原式&=\sum_{i=0}^{n}i^{t_{1}}\lfloor\frac{b}{c}\rfloor^{t_{2}}\\
&=\lfloor\frac{b}{c}\rfloor^{t_{2}}(h_{t_{1}}(n)+[t_{1}=0])
\end{aligned}
$$
* 若 $a\ge c$ 或 $b\ge c$，那么有：
$$
\begin{aligned}
原式&=\sum_{i=0}^{n}i^{t_{1}}(\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor+\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)^{t_{2}}\\
&=\sum_{i=0}^{n}i^{t_{1}}\sum_{u_{1}+u_{2}+u_{3}=t_{2}}{t_{2}\choose u_{1},u_{2},u_{3}}(\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor)^{u_{1}}(\lfloor\frac{a}{c}\rfloor i)^{u_{2}}(\lfloor\frac{b}{c}\rfloor)^{u_{3}}\\
&=\sum_{u_{1}+u_{2}+u_{3}=t_{2}}{t_{2}\choose u_{1},u_{2},u_{3}}(\lfloor\frac{a}{c}\rfloor)^{u_{2}}(\lfloor\frac{b}{c}\rfloor)^{u_{3}}\sum_{i=0}^{n}i^{t_{1}+u_{2}}(\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor)^{u_{1}}\\
&=\sum_{u_{1}+u_{2}+u_{3}=t_{2}}{t_{2}\choose u_{1},u_{2},u_{3}}(\lfloor\frac{a}{c}\rfloor)^{u_{2}}(\lfloor\frac{b}{c}\rfloor)^{u_{3}}f(a\%c,b\%c,c,n,t_{1}+u_{2},u_{1})
\end{aligned}
$$
接下来讨论一般的 $0\le a,b0\ge ai$，故 $cj+c-b\le ai$ 永远为假，因此： $$
\begin{aligned}
原式&=\sum_{j=0}^{m-1}g_{t_{2}}(j)\sum_{i=1}^{n}i^{t_{1}}[cj+c-b\le ai]\\
&=\sum_{j=0}^{m-1}g_{t_{2}}(j)\sum_{i=1}^{n}i^{t_{1}}[cj+c-b-1n$，那么： $$
\begin{aligned}
mc-b-1&>na\\
na+b+1&