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

    ID: 4847 远端评测题 1000ms 125MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>数学高精度扩展欧几里德,扩欧

【模板】有理数取余

题目描述

给出一个有理数 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 的倍数。