ForHosting KIT · 数学

Lucasの定理

巨大な階乗を使わずにC(n, k)を素数で割った余りを求めます。C(1000, 200)を7で割った余りは1で、両方を7進数で書き、桁ごとの小さな二項係数を掛け合わせて計算します。各桁を表示するので、途中の計算も確かめられます。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
N
1,000
K
200
電力(W)
7
結果
結果
1
n の桁数
6, 2, 6, 2
kの桁
4, 0, 4, 0

Lucasの定理は、nが十分に大きくnの階乗が現実的でないときに、素数を法とする二項係数を評価する標準的な方法です。その積はちょうどC(n, k) mod pであり、いずれかの下位桁が対応する上位桁を超えると全体は零になります。競技プログラミング、組合せ数論、暗号の課題では、直接の階乗が溢れるかコストが高すぎるときに、この帰着が必要です。

Lucasの定理が述べることと、必要になる場面

初等組合せ論では、二項係数C(n, k)はn元集合のk部分集合の個数を数え、nの階乗をkの階乗と(n引くk)の階乗で割ったものに等しいです。小さな素数を法とする答えだけが欲しい場合、nが数千を超えるとその閉形式は役に立ちません。中間の階乗が爆発し、浮動小数点近似は厳密な剰余を失うからです。

Édouard Lucasに因むLucasの定理は、まさにこの法に関する問題を解きます。各因子はpより小さい引数を使うため、短い乗法ループと、pが素数で分母がすべてpより小さいことから存在する法に関する逆元で計算できます。定理はpが素数であることを要求します。

合成数の法では同じ桁積は一般に正しくなく、本能力は誤った剰余を黙って返す代わりに、素数でないpを意図的に拒否します。オリンピック教材で定理に出会う学生、競技プログラミング用ライブラリを繋ぐ開発者、法算術の演習を準備する指導者は、素数仮定を強制し証明で用いる桁展開を開示する、単一の決定的関数から恩恵を受けます。

本計算機がLucasの定理を段階的に適用する方法

nとkはいずれも最大一兆までの非負整数でなければならず、pは二以上かつ百万三以下の素数でなければなりません。実装はまず型と範囲を検証し、その後pに対する決定的な試し割り素数判定を実行します。pが受理されると、解法器はnとkのp進桁を最下位から最上位へ走査します。

小さな二項係数は、Fermatの小定理(aのp引く二乗をpを法とする)による逆元付きの乗法公式を用い、公開された範囲内で精度を失わないようBigIntの厳密な中間積で実装されています。端点は安定し文書化されています。kが零またはnに等しいとき結果はpを法として一(pが一時のみ零になり得ますが、その場合は拒否されます)。

kがnを超えると結果は零。nとkがともに零のとき桁配列は単一の桁零で、結果はpを法として一です。

実務での利用、制限、料金、提供形態

数論のノートを読むとき、コンテストのサンプルを確かめるとき、法に関する組合せルーチンをデバッグするときに素早いLucas確認が欲しい場合はブラウザツールを使ってください。検証失敗と素数でない法は残高を消費しません。受理される入力は最大一兆までの非負整数n・kと、二から百万三までの素数pです。

制限のない整数C(n, k)、すべてのkに対する二項係数の行、中国剰余定理による合成数法の法二項係数が必要な場合は専用能力を使ってください。本ツールは検証済み素数pに対するLucasに意図的に止め、契約を単純で監査可能に保ちます。

競技プログラミングとオリンピック演習

競技プログラマーは大きなnに対するC(n, k) mod pをサンプルと照合でき、法が誤って合成数のときに明示的なエラーを確認できます。

数論・組合せ論の教育ラボ

指導者と学生は、Lucasの定理と素数による零判定を学ぶあいだに、法に関する積と並んでp進桁を点検できます。

pが素数でないとどうなりますか?

メッセージはpが素数でなければならないと述べます(pが合成数または1の場合など)。検証失敗は課金されません。

Lucasの定理の二項計算機は無料ですか?

ブラウザツールはお使いの端末で無料です。無効入力と素数でない法は課金されません。

n、k、pの受理範囲は?

nとkは最大1,000,000,000,000の非負整数でなければなりません。pは2から1,000,003までの素数です。範囲外の値や合成数のpは拒否されます。

C(n, k)が素数で割り切れるかはどう分かりますか?

nとkをp進数で書き、桁ごとに比べます。kのどこかの桁がnの対応する桁より大きければ結果は0で、pが二項係数を割り切ることを意味します。

C(1000, 200)を7で割った余りはいくつですか?

結果は1です。7進数の桁も下の位から表示され、1000は6, 2, 6, 2、200は4, 0, 4, 0です。200のどの桁も1000の桁を超えていません。

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

POSThttps://api.kit.forhosting.com/numth/lucas-theorem-binomial

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

curl -X POST https://api.kit.forhosting.com/numth/lucas-theorem-binomial \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":1000,"k":200,"p":7}'
{
  "n": 1000,
  "k": 200,
  "p": 7
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.lucas_theorem_binomial",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

HTTPコード意味
401unauthorizedAPIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
402insufficient_balance残高が不足しています。チャージ後に再度お試しください。
404unknown_type指定されたタスクタイプは存在しません。タイプ名を確認してください。
429rate_limitedリクエストが多すぎます。しばらく待ってから再度お試しください。

非負整数nとk、および素数の法pが与えられると、定理はnとkをp進展開し、桁ごとの小さな二項係数C(n_i, k_i)をpを法として掛け合わせます。本計算機はn、k、pを受け取り、合成数の法を明確なinvalid_inputで拒否し、決定的なLucas走査を行い、手作業で展開を再導出せずに各段を監査できるよう、法に関する結果とp進桁を返します。

Lucasの定理が述べることと、必要になる場面

nとkをp進の桁列n_iとk_iとして書き、各桁はpより厳密に小さくします。するとC(n, k)はpを法として、各iについてのC(n_i, k_i)の積と合同になります。重要な系は零判定です。 ある位置で下位桁k_iがn_iより大きいとその桁の二項係数は零であり、したがってC(n, k)はpで割り切れます。この判定だけでも「この素数で二項係数は割り切れるか」という多くの問いに、完全な積を計算せず答えられます。

本計算機がLucasの定理を段階的に適用する方法

整数フィールドn、k、pで能力を呼び出してください。合成数、一、零、負数はいずれもinvalid_inputとpを名指しするメッセージで失敗し、課金されません。各対(n_i, k_i)について、k_iがn_iを超えれば零に短絡し、そうでなければ累積積にC(n_i, k_i) mod pを掛けます。応答はn、k、p、result(零からp引く一までの剰余)、is_zero、最下位桁先頭の配列n_digitsとk_digits、および文字列lucasに設定されたmethodを返します。同じ純粋関数が無料のブラウザツールとAPI経路を駆動します。

実務での利用、制限、料金、提供形態

採点器、教育プラットフォーム、スクリプトが素数ゲートと桁走査を埋め込めずに多数のC(n, k) mod p評価を必要とする場合はAPIを使ってください。成功した各リクエストは$0.002の課金単位一件です。結果は決定的で、同じ三つ組は常に同じ剰余、同じ桁配列、同じis_zeroフラグを返します。オリンピック補助、競技プログラミングのサンドボックス、小さな素数を法とする二項係数に触れる暗号の教育デモ、近似ライブラリより厳密な法算術を好む整数パイプラインへエンドポイントを接続できます。単位は単一アイテムでエンジンは純粋なparseのため、遅延は低く保たれ、無料のWeb経路は有料APIを第二のコード経路なく映します。

課題採点器と法パイプライン

自動採点器とスクリプトは剰余を確認し、invalid_inputで素数でないpを検出し、中間積を文書化された範囲内に保てます。

このAPIでC(n,k) mod pをどう計算しますか?

整数フィールドn、k、p(pは素数)のJSONをnumth.lucas_theorem_binomialへ送ってください。成功時、応答は0..p−1のresult、is_zero、p進桁配列、method "lucas"を返します。

法に関する二項係数はどの算法で計算されますか?

Lucasの定理です。nとkをp進展開し、各桁についてC(n_i, k_i) mod pを掛けます。小さな桁の二項係数は逆元付きの乗法公式を使います。

KITの完全なドキュメントを見る →