以下の内容はhttps://kanpurin.hatenablog.com/entry/2021/08/14/115825より取得しました。

【競プロ】数学メモ

競技プログラミング メモ 典型 数論

競プロにおける数学(ほぼ数論)関連のメモ．
コンテスト中に確認できるように，細かい証明とかはせず，重要な部分だけ書く．

目次

オイラーのΦ関数

概要

正整数{n}に対して，{n}と互いに素である{n}以下の自然数の個数を{\phi(n)}とする．

性質

オイラーのΦ関数には以下のような性質がある．
  1. {\phi(mn)=\phi(m)\phi(n)} ({m,n}は互いに素)
  2. {\phi(pn)=p\phi(n)} ({n}は素数{p}を素因数に持つ)
  3. {\phi(p^n)=p^n-p^{n-1}} ({p}は素数,{1\leq n})
  4. {\displaystyle\phi(n)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)} ({p_i}は{n}の異なる素因数)
  5. {a^{\phi(n)}\equiv 1\mod n} ({n,a}は互いに素)
  6. {n}と互いに素である{n}以下の自然数の和は{\displaystyle\frac{n\phi(n)}{2}} ({2\leq n})
  7. {\displaystyle\sum_{d|n}\phi(d)=n}
  8. {n}の任意の約数を{d}として，{\gcd(x,n)=d}となる{1\leq x\leq n}の個数は{\phi(\frac{n}{d})}
  9. {\displaystyle\sum_{d|n}d\phi(d)=\prod_{i=1}^{k}\frac{1-(-p_i)^{2e_i+1}}{1+p_i}} {\displaystyle \left(n=\prod_{i=1}^{k}p_i^{e_i}\right)}
  10. {\displaystyle S_{\phi}(n)=\frac{1}{2}n(n+1)-\sum_{i=2}^{n}S_{\phi}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)} {\displaystyle\left(S_{\phi}(n)=\sum_{i=1}^{n}\phi(i)\right)}
  11. {\displaystyle\sum_{d|n}\frac{\mu^2(d)}{\phi(d)}=\frac{n}{\phi(n)}} ({\mu}：メビウス関数)

例題

問題1

{N}以下の任意の自然数と{N}の最小公倍数の総和を求めよ．
すなわち{\displaystyle\sum_{i=1}^{N}\mathrm{lcm}(i,N)}を求めよ．
制約
・{1\leq N\leq 10^{12}}

解答{\displaystyle\sum_{i=1}^{N}\mathrm{lcm}(i,N)}
{=\displaystyle N\sum_{i=1}^{N}\frac{i}{\gcd(i,N)}}
{\gcd(i,N)=d}となる{i}をまとめると
{=\displaystyle N\sum_{d|N}\sum_{\gcd(i,N)=d,1\leq i\leq N}\frac{i}{d}}
{=\displaystyle N\left(1+\sum_{d|N,d\neq N}\frac{\frac{N}{d}\phi(\frac{N}{d})}{2}\right)}
{=\displaystyle N\left(\frac{1}{2}+\sum_{d|N}\frac{\frac{N}{d}\phi(\frac{N}{d})}{2}\right)}
{=\displaystyle \frac{N}{2}\left(1+\sum_{d|N}d\phi(d)\right)}
よって{N}を素因数分解すれば{O(\sqrt{N})}で解ける．

問題2

{x}座標と{y}座標がそれぞれ{1}以上{N}以下となるような座標平面上の格子点のうち，原点{(0,0)}と線分で結んだとき他の格子点を通らないようなものの数を求めよ．
制約
・{1\leq N\leq 10^9}

解答{x}座標と{y}座標が互いに素であれば条件を満たす．したがって，{gcd(x,y)=1, (1\leq x,y\leq N)}である{(x,y)}の数を求めればよい．{x\geq y}を仮定した場合の答えが求められれば元の問題も求まるので以降これを仮定する．
{x}を固定すると{\gcd(x,y)=1}となる{y}の数は{\phi(x)}となるので{\sum_{x=1}^{N}\phi(x)}を求めればよい．
{\displaystyle S_{\phi}(n)=\frac{1}{2}n(n+1)-\sum_{i=2}^{n}S_{\phi}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)}が成り立つため，{S_{\phi}(n)}を再帰的に求めていけばよい．{\lfloor\frac{N}{i}\rfloor}としてあり得る値の集合を{V}とすると，{V}の要素は{O(\sqrt{N})}個しかないため，値ごとにまとめて計算すれば1回の再帰で{O(\sqrt{N})}で計算できる．{\lfloor\frac{\lfloor\frac{N}{s}\rfloor}{t}\rfloor=\lfloor\frac{N}{st}\rfloor}であるため，いくら再帰しても使用する値は{V}のいずれかとなる(保存しておく値は{V}だけでよい)．全体の計算量は{O(\sum_{i=1}^{\sqrt{N}}\sqrt{i})+O(\sum_{i=1}^{\sqrt{N}}\sqrt{\frac{N}{i}})=O(N^{\frac{3}{4}})}となり解ける．
また，最初の{N^{\frac{2}{3}}}要素を線形篩などで先に計算しておくことで{O(N^{\frac{2}{3}})}で解ける．*1

エラトステネスの篩

概要

{N}以下の素数を{O(N\log\log{N})}で列挙できるアルゴリズムとしてエラトステネスの篩がある．
アルゴリズムは以下の通り．

  1. {2}から{N}までの整数を用意する．
  2. {p=2}から昇順に{N}(実際は{\sqrt{N}}でいい)を越えるまで3を繰り返す．
  3. {p}が消されてないなら，残っている整数のうち{p}より大きい{p}の倍数をすべて消す(実際は{p^2}以上の{p}の倍数でいい)．
  4. 残った整数が素数．

計算量

このアルゴリズムの計算量は{N}以下の各素数{p}について倍数は{\frac{N}{p}}個あるので，全体の計算量は{O(\sum_{p\leq N, p:素数}\frac{N}{p})}となるがメルテンスの第二定理を用いると{O(N\log\log{N})}となる．

応用

このアルゴリズムの重要な点は，{2}以上{N}以下の整数{x}に対して，{x}の素因数すべてが1度ずつ{x}を篩に掛ける点である．例えば，{x=60=2^2×3×5}なら{2,3,5}が1度ずつ{x}を篩に掛ける．
つまり，このアルゴリズムは{N}以下の自然数{x}に対して，{x}の素因数を取得できるアルゴリズムであると捉えることができる．素数列挙というのは単に{x}の素因数が{x}のみであるような{x}を列挙しているに過ぎない．

例題

問題1

{2\leq x\leq N}のすべての整数{x}について，{x}の最大素因数を求めよ．
制約
・{2\leq N\leq 10^5}

解答取得した素因数の中で最大のものを求めればよい．

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

{2\leq x\leq N}のすべての整数{x}について，{x}の素因数の数(例えば{60}の素因数の数は{2,3,5}の{3}個)を求めよ．
制約
・{2\leq N\leq 10^5}

解答篩に掛けるたびにカウントすればよい．

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:])

問題3

{2\leq x\leq N}のすべての整数{x}について，「{x}と互いに素である{x}以下の自然数の個数」を求めよ．
制約
・{2\leq N\leq 10^5}

解答{\displaystyle\phi(n)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)} ({p_i}は{n}の異なる素因数)という性質を用いればよい．

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:])

線形篩

概要

エラトステネスの篩では，各合成数について，その素因数の数だけ篩に掛けていた．各合成数について，その最小の素因数だけで篩に掛けることができれば{O(N)}で素数が列挙できる．*2
{spf(n)}を{n}の最小の素因数とする．{n=spf(n)m}と表すことができ，{n}が合成数なら{spf(n)\leq spf(m)}となる．{m}の昇順に，{spf(m)}が既に求まっているなら，すでに求めた素数{p(\leq spf(m))}について{spf(pm)=p}，{spf(m)}が求まっていないなら{m}は素数であり，{spf(m)=m}として同様の計算を行っていけば素数が列挙できる．

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

上で説明したエラトステネスの篩と同様に，このアルゴリズムは素数列挙のアルゴリズムではなく{N}以下の自然数{x}に対して，{x}の最小の素因数を取得できるアルゴリズムであると捉えることができる．さらに，このアルゴリズムの嬉しい点は任意の{2\leq n\leq N}に対して，{n}を篩に掛けるときに{n=spf(n)m}と表される{m}が(合成数ならば)既に篩に掛けられている点である．{N}以下の自然数{n(=spf(n)m)}に対して，{f(n)}が{spf(n)}や{m}や{f(m)}から高速に計算できるなら，このアルゴリズムで高速に求めることができる．

乗法的関数

完全乗法的関数

任意の自然数{m,n}に対して{f(mn)=f(m)f(n)}が成り立つとき，{f}を完全乗法的関数という．{f}が完全乗法的関数ならば，{f(n)=f(spf(n)m)=f(spf(n))f(m)}であるので{n}が合成数のとき，すでに計算された{f(spf(n)),f(m)}から{f(n)}が計算できる({spf(n)}は{m}以下の素数なので{f(spf(n))}は計算されている)．{n}が素数のときに{f(n)}が高速に計算できさえすれば，{N}以下の自然数{n}に対する{f(n)}の値が高速に計算できる．

乗法的関数

互いに素な自然数{m,n}に対して{f(mn)=f(m)f(n)}が成り立つとき，{f}を乗法的関数という．{f}が乗法的関数ならば，{f(n)=f(spf(n)^{e_n}m)=f(spf(n)^{e_n})f(m)} ({e_n}は{spf(n)}が{n}を割り切る最大の回数)であるので{e_n}を高速に計算できれば完全乗法的関数と同様にして解ける．
{ e_n= \left\{ \begin{array}{ll} e_{n/spf(n)}+1 & (spf(n)=spf(n/spf(n))) \\ 1 & (otherwise) \end{array} \right. }
とすれば，同様のアルゴリズムで{e_n}や{spf(n)^{e_n}}を求めることができる．*3

性質

  1. {f(x)}と{g(x)}が乗法的関数ならば{h(x)=f(x)g(x)}も乗法的関数．
  2. {f(x)}と{g(x)}が乗法的関数ならば{h(x)=\sum_{d|x}f(d)g(x/d)}も乗法的関数．特に，{f(x)}が乗法的関数ならば{h(x)=\sum_{d|x}f(d)}も乗法的関数．*4

例題

問題1

{2\leq x\leq N}のすべての整数{x}について，「{x}と互いに素である{x}以下の自然数の個数」を求めよ．
制約
・{2\leq N\leq 10^5}

解答{p}を{n(\geq 2)}の最小素因数とする．{n}が{p^2}で割り切れるなら{\phi(n)=p\phi(n/p)}であり，割り切れないなら{\phi(n)=(p-1)\phi(n/p)}であるから線形篩のアルゴリズムを用いることで{O(N)}で求められる．

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:])

メビウス関数

概要

メビウス関数{\mu(n)}とは以下のように{1}以上の整数に対して定義される関数である．
{ \mu(n)= \left\{ \begin{array}{ll} 0 & (nが1以外の平方数で割り切れるとき) \\ (-1)^k & (nが異なるk個の素数の積であるとき) \end{array} \right. }

性質

メビウス関数には以下のような性質がある．
  1. {\mu(mn)=\mu(m)\mu(n)} ({m,n}は互いに素)
  2. {\displaystyle\sum_{d|n}\mu(d)=\left\{\begin{array}{ll}1 & (n=1) \\0 & (n > 1)\end{array}\right.}
  3. {\displaystyle S_{\mu}(n)=1-\sum_{i=2}^{n}S_{\mu}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)} {\displaystyle\left(S_{\mu}(n)=\sum_{i=1}^{n}\mu(i)\right)}
  4. {\displaystyle f(n)=\sum_{d|n}g(d)\Leftrightarrow g(n)=\sum_{d|n}\mu(n/d)f(d)}

例題

問題1

長さ{N}の数列{A}が与えられる．{1\leq i < j < k\leq N}かつ{\gcd(A_i,A_j,A_k)=1}となる{(i,j,k)}の数を求めよ．
制約
・{1\leq N,A_i\leq 10^6}

解答{ [P]= \left\{ \begin{array}{ll} 1 & (Pが真) \\ 0 & (Pが偽) \end{array} \right. }
とする．求める値は{\displaystyle\sum_{1\leq i < j < k\leq N}[\gcd(A_i,A_j,A_k)=1]}であり，{\displaystyle[n=1]=\sum_{d|n}\mu(d)}であるので
{\displaystyle\sum_{1\leq i < j < k\leq N}\sum_{d|\gcd(A_i,A_j,A_k)}\mu(d)\\ =\displaystyle\sum_{1\leq i < j < k\leq N}\sum_{d=1}^{A_{\max}}[d|\gcd(A_i,A_j,A_k)]\mu(d)}
{d|\gcd(A_i,A_j,A_k)\Leftrightarrow d|A_i\land d|A_j\land d|A_k}より
{=\displaystyle\sum_{1\leq i < j < k\leq N}\sum_{d=1}^{A_{\max}}[d|A_i\land d|A_j\land d|A_k]\mu(d)\\ =\displaystyle\sum_{d=1}^{A_{\max}}\mu(d)\sum_{1\leq i < j < k\leq N}[d|A_i\land d|A_j\land d|A_k]}
{\displaystyle\sum_{1\leq i < j < k\leq N}[d|A_i\land d|A_j\land d|A_k]}は{A}から異なる{d}の倍数を{3}つ選ぶ方法の数であるので{\displaystyle\binom{cnt(d)}{3}}となる．ただし，{cnt(d)}は{A}にある{d}の倍数の数．これは高速ゼータ変換により{O(A_{\max}\log\log{A_{\max}})}で計算できる．また，{\mu(d)}もエラトステネスの篩により{O(A_{\max}\log\log{A_{\max}})}で計算でき，線形篩なら{O(A_{\max})}で計算できる．

二項係数

概要

二項係数{\displaystyle\binom{n}{k}(0\leq k\leq n)}は{(1+x)^n}の二項展開における{x^k}の項の係数．
{\displaystyle\binom{n}{k}=\frac{n!}{k!(n-k)!}}である．

性質

二項係数には以下のような性質がある．自明な下位互換は書いてない．
ただし，{n < k}なら{\displaystyle\binom{n}{k}=0}とする．
  1. {\displaystyle\sum_{k=0}^{n}\binom{n}{k}p^{k}q^{n-k}=(p+q)^{n}}
  2. {\displaystyle\binom{n}{k}=\binom{n}{n-k}}
  3. {\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}}
  4. {\displaystyle\sum_{k=m}^{n}\binom{k}{m}=\binom{n+1}{m+1}}
  5. {\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}}
  6. {\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}=F_{n+1}} ({F_n}は{n}番目のフィボナッチ数)
  7. {\displaystyle\sum_{k=0}^{n}\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}}
  8. {\displaystyle\sum_{k=0}^{n}\binom{p+k}{k}\binom{q-k}{n-k}=\binom{p+q+1}{n}}
  9. {\displaystyle\sum_{k=m}^{n}\binom{n}{k}\binom{k}{m}=2^{n-m}\binom{n}{m}}
  10. {\displaystyle\sum_{k=-a}^{a}(-1)^{k}\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}=\frac{(a+b+c)!}{a!b!c!}}
  11. {\displaystyle\binom{n}{k}\equiv\prod_{i=1}^{m}\binom{n_i}{k_i}\bmod{p}} ({p}は素数．{n_i,k_i}は{n,k}の{p}進表記の下{i}桁目)

例題

問題1

{\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2}を求めよ．

解答{\displaystyle\sum_{k=0}^{n}\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}}で{p=q=n}とすれば
{\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}}

床関数/天井関数

実数{x}に対して床関数{\lfloor x\rfloor}は{x}以下の最大の整数と定義される．
実数{x}に対して天井関数{\lceil x\rceil}は{x}以上の最小の整数と定義される．

性質

{x,y}は実数，{m,n,a,b}は整数であるとする．
  1. {x-1 < \lfloor x\rfloor\leq x}
  2. {x \leq \lceil x\rceil < x+1}
  3. {\lfloor x\rfloor = -\lceil -x\rceil}
  4. {\lfloor n+x\rfloor = n+\lfloor x\rfloor}
  5. {\lfloor x+y\rfloor \geq \lfloor x\rfloor+\lfloor y\rfloor}
  6. {\left\lfloor \dfrac{m}{n}\right\rfloor = \dfrac{m-m\bmod{n}}{n}}
  7. {\left\lfloor\dfrac{n}{2}\right\rfloor+\left\lceil \dfrac{n}{2}\right\rceil = n}
  8. {\left\lfloor\dfrac{y}{x}\right\rfloor\geq\dfrac{y}{x}-\dfrac{x-1}{x}} ({x,y > 0})
  9. {\displaystyle\sum_{i=1}^{n-1}\left\lfloor\frac{im}{n}\right\rfloor = \frac{(m-1)(n-1)}{2}} ({m,n}は互いに素)
  10. {\displaystyle\lfloor nx\rfloor = \sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n}\right\rfloor}
  11. {\left\lfloor\dfrac{\lfloor x\rfloor}{n}\right\rfloor =\left\lfloor\dfrac{x}{n}\right\rfloor}
  12. {\left\lfloor\dfrac{n}{k}\right\rfloor (1\leq k\leq n)}の値の種類は{O(\sqrt{n})}個
  13. {\left\lfloor\dfrac{n}{k}\right\rfloor = m (m\geq 1)}となる整数{k}の範囲は{\left\lfloor\dfrac{n}{m+1}\right\rfloor +1\leq k\leq \left\lfloor\dfrac{n}{m}\right\rfloor}
  14. 床関数の和

    {\displaystyle f(a,b,m,n)=\sum_{i=0}^{n}\left\lfloor\frac{ai+b}{m}\right\rfloor}は

    • {a\geq m}または{b\geq m}のとき

    {\dfrac{n(n+1)}{2}\left\lfloor\dfrac{a}{m}\right\rfloor +(n+1)\left\lfloor\dfrac{b}{m}\right\rfloor + f(a\bmod{m},b\bmod{m},m,n)}

    • {a < m}かつ{b < m}のとき

    {n\left\lfloor\dfrac{an+b}{m}\right\rfloor -f(m,m-b-1,a,\left\lfloor\dfrac{an+b}{m}\right\rfloor -1)}

    {\displaystyle\sum_{i=0}^{n}i^{k_1}\left\lfloor\frac{ai+b}{m}\right\rfloor^{k_2}}も{O( (k_1+k_2)^3\log(n+m+a+b))}で解ける．*5

床関数の性質に性質3を適用することで天井関数の性質に変えることができる．

例題

問題1

{\displaystyle\sum_{i=1}^{N}\left\lfloor\dfrac{N}{i}\right\rfloor}を求めよ．
制約
・{1\leq N\leq 10^{12}}

解答{\lfloor N/i\rfloor =M}となる{i}の範囲が{[L,R]}であるとする．{M=\lfloor N/L\rfloor}であるので{R=\lfloor N/M\rfloor=\lfloor N/\lfloor N/L\rfloor\rfloor}となる．
したがって{(R-L+1)×\lfloor N/L\rfloor}の総和を取ればよい．計算量は{O(\sqrt{N})}

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

{\left\lfloor\dfrac{10^N}{M}\right\rfloor\bmod{M}}を求めよ．
制約
・{1\leq N\leq 10^{18}}
・{1\leq M\leq 10^9}

解答性質6を{m\leftarrow\left\lfloor\dfrac{10^N}{M}\right\rfloor , n\leftarrow M}として用いると，
{\left\lfloor\dfrac{10^N}{M}\right\rfloor\bmod{M}=\left\lfloor\dfrac{10^N}{M}\right\rfloor-M\left\lfloor\dfrac{10^N}{M^2}\right\rfloor}となる．(性質11を用いて{\left\lfloor\dfrac{\lfloor 10^N/M\rfloor}{M}\right\rfloor=\left\lfloor\dfrac{10^N}{M^2}\right\rfloor}と変換した)
さらに性質6を用いると
{\begin{array}{l} \left\lfloor\dfrac{10^N}{M}\right\rfloor\bmod{M}&=&\dfrac{10^N-10^N\bmod{M}}{M}-M\dfrac{10^N-10^N\bmod{M^2}}{M^2}\\ &=&\dfrac{10^N\bmod{M^2}-10^N\bmod{M}}{M}\\ \end{array}}
となり{O(\log{N})}で求められる．

N,M = map(int,input().split())
print((pow(10,N,M**2)-pow(10,N,M))//M)

*1:[Tutorial] Math note — Dirichlet convolution - Codeforces

*2:[Tutorial] Math note — linear sieve - Codeforces

*3:線形篩 – 37zigenのHP

*4:[Tutorial] Math note — Möbius inversion - Codeforces

*5:Floor Sum of Arithmetic Progression and Other Variants



以上の内容はhttps://kanpurin.hatenablog.com/entry/2021/08/14/115825より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14