#P18630. Cryptography Problem
Cryptography Problem
Cryptography Problem
给定 个如下形式的同余方程:
其中 是未知的随机误差,它在整数
$$-\left\lfloor\frac p{200}\right\rfloor,\ldots,\left\lfloor\frac p{200}\right\rfloor$$中均匀随机选取。 都已知。
已知存在一个未知整数 ,使这些方程成立。请恢复一个满足条件的 。
输入格式
第一行一个整数 ,表示测试数据组数。
对于每组数据:
- 第一行两个整数 ;
- 接下来 行,每行两个整数 。
输出格式
对于每组数据,输出一个整数 ,使得对所有 ,都存在整数误差 落在上述闭区间内,并满足对应的同余方程。 的取值域为原题生成时的 。
如果有多个解,可以输出任意一个。不要求输出误差。
数据范围与生成保证
,,。
保证为素数,。
原题保证 和 在 中均匀随机选取;每个 在整数闭区间 中均匀随机选取,然后计算
样例输入 1
1
50 922033901407246477
492300877907148697 8585039545574817
36478175140515505 237143454432095134
537753813197233578 694568987600933631
82789600405017625 562554784008054548
282428338659751664 111810756866364131
822189940492446170 74373256662670811
772047021157436862 845822103589054835
905076737759700460 431186334812769087
597533015463611295 721124999693760049
836526169654316522 265334775474801921
341400912803669544 720103562023164984
139669402502387585 631034499869861258
71276007772015783 514476677384034591
337347359609238003 234204423529024584
536202455504269179 767988580152404702
700544276964260742 698754372184045881
583575979672325841 181857640424161181
618636169977693774 176814568285554242
578056284566537908 901617810108821697
4593241804403846 464456491088274519
266357191672682710 882461045363140013
889969043389410586 310871528982401890
128795341091448557 735170605564908495
731543942017133872 787298395465584258
141907125229007436 782258826515419463
630216373856425575 247818711631945015
798325370867408947 797486291286888206
756453052369774682 428674547040941446
384198597100477264 730850154256353708
609227367836870855 813737668957290083
548907077218245833 261617915277192598
913671580470962359 676773938981450220
619446543059885136 542250486175077336
897794648226440556 610025381843157792
98519049764204420 82253494820699300
554347831451465947 411694162831137048
521285385565227972 25728624433720443
149842189931671659 561394698442307008
418317888425121422 124555906850617768
155742613029391582 554041506459151554
368844433342758957 590793884582829234
44214861389150265 804365813894413051
313279456314229452 355232932358357027
332914986125632240 146031583563750902
611956501645190267 124168181424207317
685356252804211145 637673787965320398
876934521572944001 565326445977039460
828894278249816206 119554705795468795
31402121026359087 895630393867204290
44811448173088972 427145243694399413
样例输出 1
578607642570710976
样例说明
原PDF为排版省略了部分样例行,并注明完整样例在比赛系统中。本题面已从公开原题下载包的01/01.a恢复全部50行,未使用省略号或补造数据。