2022-02-11 daily clock in: problem fine brush

2022-02-11 Clock in every day ： Problem fine brush

Write it at the front

“ After these things are skilled , Maybe it's as plain as drinking water , But it can bring great happiness to beginners , I always thought , Can you always keep your enthusiasm as a beginner 、 focus , Determines how far you can go when you do something , How good can you do .” This series of articles is written by python To write , There are three sources of topics ： Not done before ;Leetcode secondary , Difficult and difficult questions ; Week title ; The classic topic of a topic , All codes have been AC. everyday 1-3 Avenue , Random analysis , I hope rain or shine , As a record of encouraging yourself to brush questions .

Prison break

Relatively simple , Just recite the fast power .

mod = 100003
m, n = [int(i) for i in input().split(" ")]
ans = pow(m,n,mod)- m*pow(m-1,n-1,mod)
print(ans%mod)
        

Source code is as follows ：

def pow_mod(x, y, z):
    "Calculate (x ** y) % z efficiently."
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number

Congruence clue

Here are a few ideas ：

• Inverse element ： Inverse element is a concept in modular operation , We usually say a yes 【b model c】 Inverse element , In fact, it means a * b = 1 mod c
• Extended Euclidean method ： take $a\ast b=1\mathrm{m}\mathrm{o}\mathrm{d}c$ Turn into $a\ast b-c\ast someindividualwholeCount=1$. At this time, by asking exgcd(b, c)—> Use Euclidean algorithm to recurse until x=1,y=0 —> Reverse recursion to find the first layer x and y,x That is to say e model m Inverse element .

from math import *

def exgcd(a, b):
    if(b == 0):
        return 1,0
    # x It's back y,y yes y-x*(a//b)
    y, x = exgcd(b, a%b)
    y = y - x * (a // b)
    return x, y

a, b = map(int, input().split(' '))
x, y = exgcd(a, b)
x = (x + b) % b
print(x)

Add ：

• Proof of inverse element of extended Euclidean algorithm ：
  
• In reality, it is often applied to RSA encryption algorithm