#686. 【NFLSPC #3】五次方程

题目类型:传统型 时间限制:2500 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

题目描述

小 $L$ 在做作业,内容是解一些五次方程。由于他天天上课摸鱼,所以作业当然是不会做了。本着 “遇到困难睡大觉” 的决心,小 $L$ 去睡大觉了,于是他把问题交给了你。

给定若干五次方程 $a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+a_0=0$,求出其在 $[0,10^5]$ 内最小的整数根,保证该方程在 $[0,10^5]$ 内存在整数根。

输入格式

为了防止某些离线算法水过,本题采用强制在线。具体的方法是:

每一个方程会读入 $a_5,a_4,a_3,a_2,a_1,a_0'$,假设上一个方程的答案是 $lastans$,那么真实的方程为:$a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+(a_0' \oplus lastans)=0$。一开始,$lastans=0$。

其中 $\oplus$ 表示按位异或(xor)。

如果解密后的方程的各项系数都为 $0$,即$a_0=a_1=...=a_5=0$,即为输入结束的标志,你不需要再输出任何东西,直接结束程序即可。

输出格式

对于每一个方程,输出其在 $[0,10^5]$ 内最小的整数根。

样例输入 1

-1 15 -85 225 -274 120
6 5 4 3 2 1
0 0 0 0 0 0

样例输出 1

1
0

数据范围

$\text{subtask1(30pts)}:保证解密后 |a_i| \leq 100,方程个数 \leq 100。$

$\text{subtask2(70pts)}:无特殊限制。$

对于所有数据,满足 $|a_i| \leq 10^{12},a_0 \geq 0,方程个数 \leq 10^6$。

不保证 $a_5 \neq 0$

注:支持 __int128。

友情提醒

本题输入/输出量较大,建议使用快速输入/输出方式。实测 scanf/printf 输入输出大约需要 1s。


$by~~lqs2015$