02/19 日記 - しょぼんブログ

整数第3章と演習問題.
乗法的関数はいい感じである. $f(n)$ が乗法的関数なら, $\sum_{d \mid n} g(d) = f(n)$ となるような乗法的関数 $g(n)$ が存在することを示した. 具体的には, $n=p_1^{a_1}\cdots p_t^{a_t}$ と表されるとき, $g(n) = \prod_{i=1}^{t} \{f(p_i^{a_i}) - f(p_i^{a_i-1})\}$ となる.

メビウス反転公式というものがあって, $\displaystyle g(n)=\sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right)$ （ただし $\mu(n)$ はメビウス関数であり, $n$ に平方因子があれば $\mu(n)=0$ , そうでなければ $n=p_1\cdots p_t$ を素因数分解としたとき $\mu(n)=(-1)^t$ ）となる.
ja.wikipedia.org

この $f(n)$ に対して $g(n)$ を求める操作は微分に近い操作だと感じる. 逆に, $g(n)$ が与えられたとき $f(n)$ を求める操作は積分に近いと感じる.
たとえば, $n$ の次元を下げる（微分）と $\phi(n)$ （ $\sum_{d \mid n} \phi(d) = n$ ）, $n$ の次元を上げる（積分）と $\sigma(n)$ （ $\sum_{d \mid n} d = \sigma(n)$ ）となる.
微積分に例えたが, 数列でいえば階差数列に近いかもしれない. ぼくは数列の階差についても次元を上げるとか下げるとか, よくわからない単語を使っている. どうやら, メビウス変換という単語があるらしい. これが階差数列で言う階差と累積和で, 本当に微積分で言う微分と積分に概念が対応するかもしれない.

演習問題にあった $\phi(k) = n$ となる $k$ （具体的に, またはその数）を求める問題は面白いと思った. これをプログラミングで高速に求める方法があると良いが, それについて論文があるっぽい？ので読めたら読む. 多分知識が弱くて読めない.
oeis.org

競プロ：今日はABCだった. 201位！今日は今までコンテスト外でも解いたことのないくらいの難問がコンテスト内で解けた. 通ったときは本当に興奮した. 難易度は2686. Ex問題を見た瞬間に, F問題などはもう投げ出してこの問題に取りかかれと言われた気がした.
期待値の処理に困惑したが, まずはある程度愚直な解法を作った. 最初に愚直にやった理由は, あとに計算量削減処理が行うが, その処理が複雑で, もともと間違っていたらただ無駄な時間を過ごすからである. これは超賢明だった.