#SFCR1D. 「SFCOI-1」猜数

    ID: 278 Type: Interactive 2000ms 512MiB Tried: 31 Accepted: 11 Difficulty: 8 Uploaded By: Tags>杂项随机化数论原根最大公约数费马小定理

「SFCOI-1」猜数

题目背景

小 L 感到无聊,于是希望你来猜一个数。

题目描述

小 L 有一个质数 pp,你的任务是猜出 pp 的值。

你可以问他形式如下的问题:

axb(modp)a^x \equiv b \pmod p最小自然数解,其中 xx 为未知数。

由于你并不知道具体的 pp 值,小 L 允许你对很大的 a,ba, b 做出询问。具体地,你可以用多项式 a=F(u),b=G(v)a = F(u), b = G(v) 表示 a,ba, b,其中 1n,m1001 \leq n, m \leq 1000c1<c2<<cn10180 \leq c_1 < c_2 < \cdots < c_n \leq 10^{18}0d1<d2<<dm10180 \leq d_1 < d_2 < \cdots < d_m \leq 10^{18}0ei,fi,u,v10180 \leq e_i, f_i, u, v \leq 10^{18},$F(x) = \displaystyle\sum_{i = 1}^n e_i x^{c_i}, G(x) = \displaystyle\sum_{i = 1}^m f_i x^{d_i}$(即你可以指定这两个系数非 00 的项数不超过 100100 且最高次项的次数不高于 101810^{18} 的多项式的所有非 00 项的系数)。注意这里我们认为 00=10^0 = 1

交互格式

本题为 IO 交互题。

首先,输入一个整数 TT 表示最大交互次数。

  • 当你需要询问,按照以下格式输出。

第一行,首先一个字符串 ask,然后四个整数 n,m,u,vn, m, u, v

第二行,nn 个整数 c1,c2,,cnc_1, c_2, \cdots, c_n

第三行,mm 个整数 d1,d2,,dmd_1, d_2, \cdots, d_m

第四行,nn 个整数 e1,e2,,ene_1, e_2, \cdots, e_n

第五行,mm 个整数 f1,f2,,fmf_1, f_2, \cdots, f_m

如果有解,交互库会输出 xx 的值;否则,交互库会输出 1-1

  • 当你得到答案,按照以下格式输出。

一行,首先一个字符串 answer,然后一个整数 pp

注意:请在每次输出完后清空缓存区。

100





3





4





-1


ask 1 1 2 3
1
1
1
1

ask 3 2 1 3
0 1 2
0 1
3 1 1
3 2

ask 1 2 2 3
3
0 2
1
2 1

answer 11

样例 #1 解释

在本样例中,p=11p = 11

对于第一组询问,F(x)=G(x)=xF(x) = G(x) = xu=2,v=3u = 2, v = 3,则 a=2,b=3a = 2, b = 3。此时 x=8x = 8,返回 88

对于第二组询问,F(x)=3+x+x2F(x) = 3 + x + x^2G(x)=3+2xG(x) = 3 + 2xu=1,v=3u = 1, v = 3,则 a=5,b=9a = 5, b = 9。此时 x=4x = 4,返回 44

对于第三组询问,F(x)=x3F(x) = x^3G(x)=2+x2G(x) = 2 + x^2u=2,v=3u = 2, v = 3,则 a=8,b=11a = 8, b = 11。此时无解,返回 1-1

最后,报告 p=11p = 11,答案正确。

评测说明

本题共 77 个子任务,每个子任务内有 1010 个测试点。

你需要保证询问合法、询问次数 T\leq T 且答案正确,否则在当前测试点你将会得到 00 分。单个子任务的得分为该子任务内所有测试点得分的最小值。

数据范围

Subtask pp TT 分值
11 2p1032 \leq p \leq 10^3 T=500T = 500 10pts10 \operatorname{pts}
22 2p1062 \leq p \leq 10^6
33 同上 T=120T = 120
44 2p10102 \leq p \leq 10^{10} T=500T = 500
55 同上 T=120T = 120 20pts20 \operatorname{pts}
66 无特殊限制 T=500T = 500 10pts10 \operatorname{pts}
77 同上 T=120T = 120 30pts30 \operatorname{pts}

对于 100%100\% 的数据,2p10152 \leq p \leq 10^{15}T{120,500}T \in \{120, 500\}pp 的值不随交互过程发生变化