#P2613. 【模板】有理数取余

    ID: 1621 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>扩展欧几里德扩欧数论数学高精度

【模板】有理数取余

题目描述

给出一个有理数 c=abc=\frac{a}{b},求 cmod19260817c \bmod 19260817 的值。

这个值被定义为 bxa(mod19260817)bx\equiv a\pmod{19260817} 的解。

输入格式

一共两行。

第一行,一个整数 aa
第二行,一个整数 bb

输出格式

一个整数,代表求余后的结果。如果无解,输出 Angry!

233
666

18595654

提示

对于所有数据,保证 0a10100010\leq a \leq 10^{10001}1b10100011 \leq b \leq 10^{10001},且 a,ba, b 不同时是 1926081719260817 的倍数。