逆元

题目描述

给出一个有理数$c=\frac{a}{b}$ ，求$cmod19260817$的值。

输入格式

一共两行。

第一行，一个整数$a$。
第二行，一个整数$b$。

输出格式

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

题解

对于$c=\frac{a}{b}$求$cmod19260817$，相当于求$\frac{a}{b}mod19260817$也就是$a\times b^{-1}mod19260817$

之后我们求个逆元就行啦。

$exgcd$求逆元证明（倒推）：

$$ax+by=1$$

$$axmodb+bymodb=1modb$$

$$axmodb+0=1modb$$

$$axmodb=1modb$$

$$ax\equiv 1(\mathrm{mod}b)$$

Code (不要打我，懒得高精)

#!/usr/bin/python3
# -*- coding: UTF-8 -*-
 
def exgcd(a, b):      # 求exgcd
    if(b == 0):
        x = 1
        y = 0
        return x, y
    x, y = exgcd(b, a % b)
    tx = x
    x = y
    y = tx - (a // b) * y
    return x, y
 
mod = 19260817
a = int(input())
b = int(input())
if (b == 0):    # 0不能做除数
    print("Angry!")
else:
    x, y = exgcd(b, mod)
    x = (x % mod + mod) % mod
    print(a*x % mod)

THE END