CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「タンジェント・フラクション」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
tan(正接)が単位分数となる角度を探す問題でした。
一見すると図形の問題のようですが、実際は整数の約数に関する問題です。

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

問題のおさらい

α と β を、0 < α < β < π/2 を満たす実数とします。

α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします。)

例えば下図の青色の正方形の格子において、図のように α(≒0.3218)と β(≒0.4636)をとると、tan(α)=1/3, tan(β)=1/2 です。
さらに黒色の三角形が直角二等辺三角形となるため、tan(α+β)=1 となり、このような α と β が題意を満たすことが分かります。

正の実数 m に対し、m ≦ α+β の範囲で題意を満たす α, β の組の個数を F(m) と定義します。

例えば F(0.5)=1,F(0.3)=4,F(0.1)=15,F(0.01)=266 となることが確かめられます。

標準入力から、正の実数 m(0.001 < m < 1)が与えられます。
標準出力に F(m) の値を出力するプログラムを書いてください。
なお入力値の小数点以下の桁数は最大で 4 桁とします。

方針:加法定理からの因数分解で考えよう

何を差し置いても、本問はまずは tan の加法定理を用いることから始まります。tan の加法定理は覚えているでしょうか。「いちマイタンタン、タンプラタン」なんて語呂で覚えた方もいらっしゃるかもしれません。忘れていた人も、検索して公式を見つけてきましょう。

参考:三角関数(Wikipedia)

本問では、tan(α), tan(β), tan(α+β) がすべて単位分数となるα, βを探します。自然数 p, q, r を用いて、tan(α), tan(β), tan(α+β) をそれぞれ 1/p, 1/q, 1/r と表します。これらを上の公式に代入すると、次のようになります。

左辺の分母・分子に pq をかけ、さらに両辺の分母を反対側に移します。次のようになります。

本問は要するに、上式を成立させる自然数の組 (p, q, r) がいくつあるかを問うているわけです。

そのような (p, q, r) を探すコードを書けばよいのですが、ここで問題が生じます。調べるべき変数の範囲が分からないという問題です。r については分かります。m ≦ α+β という条件が与えられています。両辺に tan を作用させて tan(m) ≦ tan(α+β)、右辺はイコール 1/r ですから、両辺の逆数をとり、r ≦ 1/tan(m) と、r の範囲が分かります。

一方、p, q はすんなりと範囲を絞りこめません。この条件で、どうやって解を求めたらよいでしょうか?

そこで、次のような式変形を行いましょう。因数分解された形で考える ことがポイントです。

右辺の r2+1 を、rprq の積として表すことができました。ここから分かるのは、rp(または rq)は r2+1 の約数であるということです。r の値を一つ固定し、r2+1 の約数が見つかれば、そこから pq の値は一意に定まります。つまり本問は、さまざまな r に対し、r2+1 の約数を探して数えるコードを書けばよいということです。

なおそのような数を探すときには、1 から r2+1 までの全ての数で割り算を試す必要はなく、1 から r の範囲だけの割り算で構いません。(この考え方は今までにも何度か登場しています:数学の問題をプログラミングで解こう!「コード・トライアスロン2」問題解説 第 2 問) 本問では α < β の条件から、pq ですので、1 から r の範囲で r2+1 を割り切る整数の個数そのものが、求めるべき答えになります。

コード例(Python)になります。

import math

m = float(input())
n = int(1.0 / math.tan(m))

answer = 0
for r in range(1, n+1):
    s = r*r+1
    for d in range(1, r+1):
        if s % d == 0:
            answer += 1
print answer

篩(ふるい)で約数の探索を高速化!

上記のコードで 1 秒の制限時間でのクリアは可能ですが、以下では上級編として、ちょっとした高速化を紹介します。

上のコードでは、様々な r に対する r2+1 の約数の個数を探すために、一つ一つ割り算を試していました。次の方法では、篩(ふるい)を使って約数の探索を高速化します。

2 種類の配列を用意します。一つは、各 r に対し r2+1 の値で初期化します。もう一つは約数の個数を保存するための配列で、1 で初期化します。(下図では r=10 まで記しています。)

r2+1 の配列を左から順に見ていきます。1 でない値があったとき、その値はかならず素数です(*)。そのような素数を P とおき、このときの rr‘ とおきます(r2+1 = P)。ここから右に P 列おきの r2+1 の値は、どれも P で割り切れます。(なぜなら、整数 k を用いてそのような rr‘+Pk と書くと、r2+1 の値は (r‘+Pk)2+1 = (r2+1)+2rPkP2k2P+2rPkP2k2P×(1+2rkPk2) と、P の整数倍として書けるためです。)

r=1 から始めて、配列を右に 2 列おきに見ていき、途中の値を 2 で割り尽くしていきましょう。このとき、各マスについて、(2 で割れた回数+1) の値を、下の配列の値に乗じます。(ある整数が p1e1p2e1・…・pmem のように素因数分解されるとき、約数の個数は (e1+1)・(e2+1)・…・(em+1) と表されるためです。)結果、配列は次のようになります。

以下、同様の処理を続けましょう。次は r=2 のときの r2+1 の値 5 で配列を更新します。

次は r=3 のときの r2+1 の値 5 で配列を更新します。

最終的な配列の状態は以下です。下の配列に、各 r に対する r2+1 の約数の個数ができあがっています。この部分の和(pq を考慮して 2 で割った値)が求めるべき答えです。

コード例は以下です。始めのコードよりもずっと高速です。

import math

m = float(input())
n = int(1.0 / math.tan(m))
a = [i*i+1 for i in range(n+1)]
b = [1 for i in range(n+1)]

for i in range(1, n+1):
    if a[i] == 1: continue
    p = a[i]
    for j in range(i, n+1, p):
        e = 0
        while a[j] % p == 0:
            e += 1
            a[j] /= p
        b[j] *= e + 1

answer = 0
for i in range(1, n+1):
    answer += b[i] / 2
print answer

(*) r2+1 の配列に 1 でない数が現れればそれは素数である、というのは自明でないかもしれません。背理法で考えましょう。もしこの数が合成数だと仮定すると、その素因数のうち少なくともどれか一つは r2+1 の平方根よりも小さく、今回の場合は r 未満であるはずです。ならば、そのような素因数はそれよりも前にすでに現れているはず。この位置で現れたという仮定と矛盾します。

みんなのコード

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

CodeIQ「タンジェント・フラクション」問題 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 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 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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