CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「プライム・ペア」問題解説

2017.03.17 Category:CodeIQ問題解説・リーダーボード Tag:

  • 5
  • このエントリーをはてなブックマークに追加

「数学の問題をプログラミングで解こう!」シリーズ。
オイラーのφ関数という関数を題材にした問題でした。定理をうまく活用することがポイントです。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

問題のおさらい

自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。

(F(k) はオイラーのφ関数とも呼ばれています。参考:オイラーのφ関数(Wikipedia)

例えば F(12)=4 です。1 から 12 のうち 12 と互いに素なのは 1, 5, 7, 11 の 4 つです。

標準入力から、自然数 n(1 ≦ n ≦ 105)が与えられます。
標準出力に F(n!) を 1000003 で割った余りを出力するプログラムを書いてください。

例えば n=10 のとき、F(10!)=F(3628800)=829440 です。

同様に、F(20!) を 1000003 で割った値は 961998 です。

方針―定理をうまく使おう

巨大な数について、互いに素な整数の個数を求める問題です。

一般に、ある二つの整数が互いに素かどうか調べるには、ユークリッドの互除法という方法で最大公約数を求め、それが 1 かどうかをチェックするという方法があります。

参考:ユークリッドの互除法(Wikipedia)

この方法を使って F(k) を求めるには、1 から k までの自然数についてチェックを行い、k との最大公約数が 1 になるものを数えればよいです。次のようなコードになります(python)。

D = 1000003 
n = int(input())

def gcd(x, y):
    return gcd(y % x, x) if x > 0 else y

f = 1
for i in range(1, n+1): f *= i

answer = 0
for i in range(1, f+1):
    if gcd(f, i) == 1: answer += 1

print answer % D

しかし本問では kn! と巨大です。このような総当たりの方法は到底うまくいきませんので、別の方法を考えましょう。

そこで、まずは本文でリンクされている Wikipedia の記事を読み込んでみましょう。いろいろと興味深い定理が紹介されています。その中でも次の定理は、本問を解くためにたいへん有用です。(変数名を本問の表現に合わせています。)

これはどういう意味でしょうか? 1 行目の記号Π(パイ)は、和の記号Σ(シグマ)の積バージョンです。例えば 24 を素因数分解すると 24 = 23×31 です。このような形で k の素因数分解が表されたなら、φ(k) は 2 行目の式で簡単に計算できてしまうのです。

上の k = 24 を例にすると、(p1, e1) = (2, 3), (p2, e2) = (3, 1) です。これを 2 行目の式に当てはめて、次のように φ(24) = 8 と求められます。

つまり、n! を素因数分解した形で表せられれば、総当たりをせずとも、上の公式で答が出せるということです。

残るは n! を素因数分解した形でどうやって表すかです。素因数 p = 2 だと、n! の中に素因数 2 がいくつあるかを考えます。下のような図を考えると分かりやすいです。

マル 1 つが素因数 2 に対応します。これを横方向に見ます。一番下の行には、偶数の位置にマルが一つずつあります。その次の行には、4 の倍数の位置にマルがあります。以降、8 の倍数、16 の倍数、…とマルがあります。マルの合計の個数は、|n÷21|+|n÷22|+|n÷23|+|n÷24|+… と計算できます。(|・| は小数点以下を切り捨てる演算です。)

実装

以上でコードを書く準備が整いました。まずは素数のリストを作ります。これにはエラトステネスの篩のアルゴリズムが使えます。次に、素数の一つ一つについて、上の方法で n! の素因数の個数を計算します。

最後に Φ(k) の公式に当てはめます。piei の計算が最後の難関です。ここではべき剰余として知られる方法があるので用いましょう。

参考:冪剰余(Wikipedia)

コード例は以下です。

import math

D = 1000003 
n = int(input())

# a^n (mod p)
def pow_mod(a, n, p):
    if n == 0: return 1
    if n % 2 == 0: return pow_mod(a*a%p, n/2, p)
    return a * pow_mod(a, n-1, p) % p

# エラトステネスの篩で素数のリストを作る
sieve = [False]*(n+1)
primes = []
rootn = int(math.sqrt(n))
for p in range(2, rootn+1):
    if sieve[p] == True: continue
    for q in range(2*p, n+1, p): sieve[q] = True
for p in range(2, n+1):
    if sieve[p] == False: primes.append(p)

# 各素数pについてn!の素因数の個数eを求め
# answerにp^e-p^(e-1)をかけていく
answer = 1
for p in primes:
    e, q = 0, p
    while q <= n:
        e += n / q
        q *= p
    a = pow_mod(p, e, D) - pow_mod(p, e-1, D)
    answer = (answer * a) % D

print answer

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「プライム・ペア」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 5
  • このエントリーをはてなブックマークに追加

■関連記事

数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。 例えば F(12, 5)=4 です。 12!(=479001600)は 5 で最大 2 回割ることができ...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説... 問題のおさらい n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...
数学の問題をプログラミングで解こう!「タンジェント・フラクション」問題解説... 問題のおさらい α と β を、0 < α < β < π/2 を満たす実数とします。 α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ