マスター・オブ・整数で競技プログラミングその１

マスター・オブ・整数とは

マスター・オブ・整数とは，雑誌「大学への数学」の分野別充填シリーズ。主に難関大学を目指す高校生向けの書籍である。競技プログラミングに高校数学の整数分野の知識，テクニックが役に立つとよく聞くので冬休みを利用して解き進めることにした。できる範囲で問題を競技プログラミングっぽく言い換えてみたり，それに対してのコーディングを行ったりしたいと考えている。著作権のことがよくわからないので，具体的な問題等は伏せながら進めたいと思う。

１.素因数分解の利用（１）約数の個数

約数の個数

$N$ の約数を調べるには素因数分解すればよい。 $N = p ^ {a_1} _1 \cdot p ^ {a_2} _2 \cdot \cdots \cdot p ^ {a_n} _n$ のとき， $N$ の約数の個数は $(a _1 + 1) \times (a _2 + 1) \times \cdots \times (a _n + 1)$ で得られる。約数は（重複を含む）すべての素因数から適当に数を選んで掛け合わせることで得られる。素因数 $p _ i$ を使える個数は０個～ $a _i$ 個までの $a _ i + 1$ 通りである。それをすべての素因数について何個使うかを決めれば約数が一つ定まるということである。

#入力で与えれらえた自然数Ｎの約数の個数を求める。

#nの素因数をリストに格納する
def func(n):
    while n%2 == 0:
        n //= 2
        P.append(2)
    i = 3
    while i*i <= n:
        if n%i == 0:
            n //= i
            P.append(i)
        else:
            i += 1
    if n != 1:
        P.append(n)

#入力を受け取る
N = int(input())
#素因数を格納するためのリスト
P = []
func(N)
ans = 1
for p in set(P):
    cnt = P.count(p)
    ans *= cnt + 1
print(ans)

約数の総和

$N = p ^ {a_1} _1 \cdot p ^ {a_2} _2 \cdot \cdots \cdot p ^ {a_n} _n$ のとき， $N$ の約数の総和は $(1+p ^ 1 _ 1 + p ^ 2 _ 1 + \cdots + p ^ {a _1} _ 1) \times \cdots \times(1+p ^ 1 _ n + p ^ 2 _ n + \cdots + p ^ {a _n} _ n)$ で与えられる。

上式を展開したときにできる項１つ１つがＮの約数になっている。さきほどの約数の個数の説明で，素因数 $p _ i$ を使う方法は $a _ i + 1$ 通りと書いたが，その $a _ i + 1$ 通りの具体的な使い方が $(1+p ^ 1 _ 1 + p ^ 2 _ 1 + \cdots + p ^ {a _1} _ 1)$ である。総和を求めるには，先ほどのコードの出力部分を少し変更するだけでできる。各素因数についてのカッコの中の足し算を先に計算しておく方が実装が簡単と思われる。

ans = 1
for p in set(P):
    pro = 0
    cnt = P.count(p)
    for i in range(cnt+1):
        pro += p**i
    ans *= pro
print(ans)

約数の総積

総和は良く聞くが，総積という言葉はあまり聞かない（私も聞いたことはない）。要はすべての約数の積はどうなるかということである。 $a$ が $N$ の約数だとすると， $\frac{N}{a}$ も $N$ の約数となることを利用する。 $N$ の約数を小さい順に並べて以下のようになっていたとする $a _1, a_2, \cdots a_n$ （もちろん $a _1 = 1, a _n = N$ である）すると $a _ 1 \times a _ n = N$ となる。また，すべての約数に対して同様のペアが必ず存在する。約数の個数の求め方は最初に紹介した通りである。今，約数が全部で $2n$ 個あるとすると2つの約数の積が $N$ となる組み合わせが $n$ 個存在するので，求める値は $N ^ {n}$ である。

pow = 1
for p in set(P):
    cnt = P.count(p)
    pow *= cnt+1
print(N**(pow//2))

ある自然数を連続する自然数の和で表す方法

素直に考える。 1～ $L$ までの自然数の和は $\sum ^{L} _{i=1} i = \frac{1}{2} L (L+1)$ なので， $k+1$ ～ $L$ までの和は

$\sum ^{L} _{i=1} i - \sum ^{k} _{i=1} i = (n-k)(n+k+1)$

従って，入力Nに対して条件を満たすような連続する自然数列を求めるには $(n-k)(n+k+1) = N$ を満たす自然数 $n, k$ の組を求めればよい。

しかし，方程式を解くのは，コンピュータはあまり得意ではなさそうなので，違う考察が必要である。

まず，連続する奇数個の整数でＮを表すことを考える。そのような整数列は（奇数個なので）真ん中の数があり，またその数に関して左右対称である。今， $m$ 個の数列で，その真ん中の数を $A$ とすると $m \times A = N$ （※）となっている。この $m$ 個の数列の中に0以下の数が含まれていなければ，これは求めるべき連続する自然数列である。次に，0以下の整数が含まれている場合について考える。このときは必ず0が含まれているので，0を真ん中として左右対称な部分列で和が0になるようなものが必ず存在する。例えば，和が9になるような列を以下のようにとったとき $(-3) + (-2) + (-1) + 0 + 1 + 2 + 3 + 4 + 5$ $(-3) + (-2) + (-1) + 0 + 1 + 2 + 3 = 0$ であるので，この部分を取り除くことにより，連続する偶数個の自然数列に変形することができる。また，逆に連続する偶数個の自然数列に上述のような数列をつなげることで，和の値を保ったまま奇数個の整数列に変えることができる。従って，和がNになるような連続する奇数個の整数列の個数と，連続する自然数列の個数は一致するので，前者を求めることにする。そのような数列の個数は（※）の考察により，奇数の約数の個数と一致する。