逆元

题目描述

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

输入格式

一共两行。

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

输出格式

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

题解

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

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

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

$$ax + by = 1$$

$$ax \bmod b + by \bmod b = 1 \bmod b$$

$$ax \bmod b + 0 = 1 \bmod b$$

$$ax \bmod b=1 \bmod b$$

$$ax\equiv 1 \pmod 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