CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

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

みなさんはうまくできましたか?
ぜひ出題者の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 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...
数学の問題をプログラミングで解こう!「タンジェント・フラクション」問題解説... 問題のおさらい α と β を、0 < α < β < π/2 を満たす実数とします。 α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします...
数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説... 問題のおさらい 自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置することを考えます。 このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。 例えば以下は、(n, k)=(4, 5) のときの駒の配置例を示...
数学の問題をプログラミングで解こう!「クロッシング・ワード」問題解説... 問題のおさらい クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。 以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。 白マス・黒マスの配置には次のルールがあります。 黒マスによって白マスの領域が分断されてはならない。 黒マスが縦・横に連続し...
数学の問題をプログラミングで解こう!「ルーム・アンド・ルーフ」問題解説... 問題のおさらい 一辺の長さが 1 の正方形を考えます。これを P0 と呼びます。 各頂点を時計回りに A, B, C, D とします。 P0 に対し、次の手順で新しい正方形を描きます。 辺 BC と同じ辺を持つ正三角形 BCE を P0 の外側に描きます。 D と E を線分で結びます。 そして...
数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説... 問題のおさらい 9606+91377 という足し算を筆算で行いましょう。下のようになります。 この計算では繰り上がりがあります。 例えば、一の位を足すと 6+7=13 です。このとき、十の位に 1 を繰り上げます。 十の位は、繰り上げた 1 を足して、1+0+7=8 と計算します。 同様に、...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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