競プロにおける数学(ほぼ数論)関連のメモ.
コンテスト中に確認できるように,細かい証明とかはせず,重要な部分だけ書く.
オイラーのΦ関数
概要
正整数に対して,と互いに素である以下の自然数の個数をとする.性質
オイラーのΦ関数には以下のような性質がある.例題
座標と座標がそれぞれ以上以下となるような座標平面上の格子点のうち,原点と線分で結んだとき他の格子点を通らないようなものの数を求めよ.問題2
制約
・
エラトステネスの篩
概要
以下の素数をで列挙できるアルゴリズムとしてエラトステネスの篩がある.アルゴリズムは以下の通り.
- からまでの整数を用意する.
- から昇順に(実際はでいい)を越えるまで3を繰り返す.
- が消されてないなら,残っている整数のうちより大きいの倍数をすべて消す(実際は以上のの倍数でいい).
- 残った整数が素数.
計算量
このアルゴリズムの計算量は以下の各素数について倍数は個あるので,全体の計算量はとなるがメルテンスの第二定理を用いるととなる.応用
このアルゴリズムの重要な点は,以上以下の整数に対して,の素因数すべてが1度ずつを篩に掛ける点である.例えば,ならが1度ずつを篩に掛ける.つまり,このアルゴリズムは以下の自然数に対して,の素因数を取得できるアルゴリズムであると捉えることができる.素数列挙というのは単にの素因数がのみであるようなを列挙しているに過ぎない.
例題
問題1
のすべての整数について,の最大素因数を求めよ.
制約
・
解答
取得した素因数の中で最大のものを求めればよい.N = int(input()) ans = list(range(N+1)) for i in range(2,N+1): # 素数ならans[i]=iとなっている if ans[i] != i: continue for j in range(i*2,N+1,i): ans[j] = i print(ans[2:])
この問題は高速な素因数分解のために用いられたりもする.
のすべての整数について,の素因数の数(例えばの素因数の数はの個)を求めよ.問題2
制約
・解答
篩に掛けるたびにカウントすればよい.
N = int(input()) ans = [0]*(N+1) for i in range(2,N+1): if ans[i] != 0: continue for j in range(i,N+1,i): ans[j] += 1 print(ans[2:])
N = int(input()) ans = list(range(N+1)) for i in range(2,N+1): if ans[i] != i: continue for j in range(i,N+1,i): ans[j] = ans[j] // i * (i-1) print(ans[2:])
線形篩
概要
エラトステネスの篩では,各合成数について,その素因数の数だけ篩に掛けていた.各合成数について,その最小の素因数だけで篩に掛けることができればで素数が列挙できる.*2をの最小の素因数とする.と表すことができ,が合成数ならとなる.の昇順に,が既に求まっているなら,すでに求めた素数について,が求まっていないならは素数であり,として同様の計算を行っていけば素数が列挙できる.
spf = [0] * (N+1) prime = [] for m in range(2,N+1): if spf[m] == 0: spf[m] = m prime.append(m) for p in prime: if p > spf[m] or p*m > N: break spf[p*m] = p
上で説明したエラトステネスの篩と同様に,このアルゴリズムは素数列挙のアルゴリズムではなく以下の自然数に対して,の最小の素因数を取得できるアルゴリズムであると捉えることができる.さらに,このアルゴリズムの嬉しい点は任意のに対して,を篩に掛けるときにと表されるが(合成数ならば)既に篩に掛けられている点である.以下の自然数に対して,がややから高速に計算できるなら,このアルゴリズムで高速に求めることができる.
乗法的関数
完全乗法的関数
任意の自然数に対してが成り立つとき,を完全乗法的関数という.が完全乗法的関数ならば,であるのでが合成数のとき,すでに計算されたからが計算できる(は以下の素数なのでは計算されている).が素数のときにが高速に計算できさえすれば,以下の自然数に対するの値が高速に計算できる.
例題
問題1
のすべての整数について,「と互いに素である以下の自然数の個数」を求めよ.
制約
・
解答
をの最小素因数とする.がで割り切れるならであり,割り切れないならであるから線形篩のアルゴリズムを用いることでで求められる.spf = [0] * (N+1) phi = [0] * (N+1) prime = [] for m in range(2,N+1): if spf[m] == 0: spf[m] = m phi[m] = m-1 prime.append(m) for p in prime: if p > spf[m] or p*m > N: break spf[p*m] = p if m%p == 0: phi[p*m] = p*phi[m] else: phi[p*m] = (p-1)*phi[m] print(phi[2:])
メビウス関数
概要
メビウス関数とは以下のように以上の整数に対して定義される関数である.性質
メビウス関数には以下のような性質がある.- (は互いに素)
例題
問題1
長さの数列が与えられる.かつとなるの数を求めよ.
制約
・
二項係数
概要
二項係数はの二項展開におけるの項の係数.である.
性質
二項係数には以下のような性質がある.自明な下位互換は書いてない.ただし,ならとする.
例題
問題1
を求めよ.
解答
でとすれば床関数/天井関数
実数に対して床関数は以下の最大の整数と定義される.実数に対して天井関数は以上の最小の整数と定義される.
性質
は実数,は整数であるとする.- ()
- (は互いに素)
- の値の種類は個
- となる整数の範囲は
床関数の性質に性質3を適用することで天井関数の性質に変えることができる.
例題
問題1
を求めよ.
制約
・
解答
となるの範囲がであるとする.であるのでとなる.したがっての総和を取ればよい.計算量は
N = int(input()) ans = 0 L = 1 while L <= N: R = N // (N // L) ans += (R - L + 1) * (N // L) L = R + 1 print(ans)
を求めよ.問題2
制約
・
・解答
性質6をとして用いると,
となる.(性質11を用いてと変換した)
さらに性質6を用いると
となりで求められる.
N,M = map(int,input().split()) print((pow(10,N,M**2)-pow(10,N,M))//M)