UOJ Logo Universal Online Judge

UOJ

#499. 新年的邀请函

附件下载 统计

过年了,可是由于肺炎疫情突发,鼠们纷纷委婉地拒绝参加新年宴会。结果偌大的宴会只有皮卡丘和跳蚤明确表明自己要赴约。

如果在这个节骨眼宴会现场被猫们围攻,那么只有皮卡丘能逃出去,跳蚤就凉了(虽然抓它好像没什么用,又不能吃)。

所以为了对外隐瞒宴会实际参加的人数,不引起恐慌,跳蚤提高了宴会现场的防卫等级:必须出示邀请函或者正确回答通关密码才能进入会场。

通关密码为一个在 $1$ 到 $m$ 之间均匀随机的质数 $p$。也即,先找出 $1 \le q \le m$ 的所有质数 $q$,然后再在这些质数中均匀随机出一个质数 $p$。

每名与会者的邀请函上有一个在 $1$ 到 $n$ 之间均匀随机出来的整数,第 $i$ 位与会者的邀请函上写的是 $a_i$。

此外,每个邀请函上还有一个整数 $t_i$:如果存在数字 $x$ 满足 $x^2 \equiv a_i \pmod p$,则 $t_i = 1$,否则 $t_i = -1$。

猫猫自然是不可能拿到邀请函了,但皮卡丘有情报表明猫猫已经窃取了跳蚤的邮箱,获取了 $100000$ 个邀请函上的 $a_i, t_i$。

因此,皮卡丘想知道假如情报属实,猫猫能不能猜出通关密码是多少?如果能猜出来,那他得赶紧警告跳蚤了。

为此,皮卡丘准备写个程序试试……

输入格式

第一行两个正整数 $n$,$m$,含义如前所述。

之后 $100000$ 行,第 $i$ 行一个正整数 $a_i$和一个整数 $t_i$。如果存在数字 $x$ 满足 $x^2 \equiv a_i \pmod p$,则 $t_i = 1$,否则 $t_i = -1$。

输出格式

一行一个整数,表示素数 $p$

样例一

见“样例数据下载”

explanation

样例一中,$n$ = $10000$,$m$ = $1000000$。容易发现,$1$ 到 $m$ 中只有一个素数符合条件。

样例二

见“样例数据下载”

限制与约定

测试点编号$n$$m$
$1$$=10^4$$= 10^6$
$2$$=10^6$$=10^9$
$3$$=10^9$$=10^9$
$4$$=10^9$$=10^{10}$
$5$$=10^6$$=10^{11}$
$6$$=10^9$$=10^{11}$
$7$$=10^6$$=10^{12}$
$8$$=10^7$$=10^{12}$
$9$$=10^8$$=10^{12}$
$10$$=10^9$$=10^{12}$

保证对于每个点,恰有一个素数 $p$ 满足要求。

时间限制:$\texttt{1s}$

空间限制:$\texttt{1024MB}$

下载

样例数据下载