I tried to solve AOJ's number theory with Python

Introduction

Hello. It's chewy and chewy. I tried to solve AOJ's number theory in Python.

It's been less than half a year since I started programming myself AtCoder is green, so I'm not a strong man.

Since there are few articles on AOJ, my record I hope it will support the comrades who will do their best with Python. I tried together.

Ah, let's go

table of contents

NTL_1_A : Prime Factorization NTL_1_B : Power NTL_1_C : Least Common Multiple NTL_1_D : Euler's Phi Function NTL_1_E : Extended Euclid Algorithm

NTL_1_A : Prime Factorization


#input
n = int(input())

#Factors into prime factors and stores the factors in a list
def fac(n):
    f_n = n
    l = []
    if n==1:
        l.append(1)
        exit()
    
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            n //= i
            l.append(i)
    if n!=1:
        l.append(n)
    
    return print("{0}:".format(f_n),*l)

fac(n)

NTL_1_B : Power

 #pow tsuyo oi
m,n = map(int,input().split())
mod = 10**9+7

print(pow(m,n,mod))

NTL_1_C : Least Common Multiple

n = int(input())
a = list(map(int,input().split()))

#gcd and lcm functions
def gcd(a,b):
    a,b = min(a,b), max(a,b)
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

from functools import reduce
ans = reduce(lcm,a)
print(ans)

NTL_1_D : Euler's Phi Function

There seems to be something like this ↓ Euler's φ function (https://mathtrain.jp/phi)

n = int(input())
l = []
def fac(n):
    if n==1:
        l.append(1)
        exit()
    else:
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                while n%i==0:
                    n //= i    
                l.append(i)
        
        if n!=1:
            l.append(n)
    
    return l

fac(n)
ans = n
for i in l:
    ans *= (1-1/i)
print(int(ans))

NTL_1_E : Extended Euclid Algorithm

This article is easy to understand. I am always indebted. Extended Euclidean algorithm (https://qiita.com/drken/items/b97ff231e43bce50199a)

#Extended Euclid
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



x,y = map(int,input().split())
a,b,c = egcd(x,y)

if x==y:
    print(0,1)
    exit()

print(b,c)

in conclusion

This is my first article, so be gentle

Recommended Posts

I tried to solve AOJ's number theory with Python
I tried to solve the soma cube with python
I tried to solve the problem with Python Vol.1
I wanted to solve ABC172 with Python
I wanted to solve NOMURA Contest 2020 with Python
I tried to output LLVM IR with Python
I tried to automate sushi making with python
I want to solve APG4b with Python (Chapter 2)
I tried fp-growth with python
I tried scraping with Python
I tried to discriminate a 6-digit number with a number discrimination application made with python
I tried scraping with python
How to write offline real time I tried to solve E12 with python
I tried to implement Minesweeper on terminal with python
I tried to get started with blender python script_Part 01
I tried to touch the CSV file with Python
I tried to get started with blender python script_Part 02
I tried to implement an artificial perceptron with python
I tried to automatically generate a password with Python3
I tried to analyze J League data with Python
I tried to touch Python (installation)
I tried web scraping with python.
I want to debug with Python
I tried running prolog with python 3.8.2.
I tried SMTP communication with Python
I tried to find the entropy of the image with python
I tried to simulate how the infection spreads with Python
I wanted to solve the Panasonic Programming Contest 2020 with Python
I tried to make various "dummy data" with Python faker
I tried various methods to send Japanese mail with Python
I tried to solve a combination optimization problem with Qiskit
[Python] I tried to visualize tweets about Corona with WordCloud
Mayungo's Python Learning Episode 3: I tried to print numbers with print
I tried to make GUI tic-tac-toe with Python and Tkinter
I tried to divide the file into folders with Python
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
The 15th offline real-time I tried to solve the problem of how to write with python
[5th] I tried to make a certain authenticator-like tool with python
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to implement Autoencoder with TensorFlow
I tried to implement permutation in Python
[2nd] I tried to make a certain authenticator-like tool with python
I tried to visualize AutoEncoder with TensorFlow
How to write offline real time I tried to solve the problem of F02 with Python
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
I tried to get started with Hy
I tried scraping Yahoo News with Python
I tried to implement PLSA in Python 2
[3rd] I tried to make a certain authenticator-like tool with python
[Python] A memo that I tried to get started with asyncio
Python3 standard input I tried to summarize
I tried sending an email with python.
I tried to create a list of prime numbers with python
I tried non-photorealistic rendering with Python + opencv
[Pandas] I tried to analyze sales data with Python [For beginners]
I want to play with aws with python
I tried to fix "I tried stochastic simulation of bingo game with Python"
I tried to make a periodical process with Selenium and Python
I tried to let optuna solve Sudoku
I tried a functional language with Python