ForHosting KIT · 開発者向けツール

2種類の互いに素な硬貨で目標額を表せるか判定

2種類の硬貨による表現可能性チェッカーは、指定された2つの額面をそれぞれ0枚以上使って、非負の目標値をちょうど作れるか判定します。額面は互いに素である必要があり、その条件により合同算術を用いた厳密な解法が利用できます。表現できる場合は正確な硬貨枚数の組を返し、できない場合は該当する組が存在しないことを明示します。数値実験、離散数学の演習、額面設計、総当たりを避けた固定数量の組合せ確認などにご利用いただけます。

● Beta無料・ブラウザ内で実行

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

2硬貨問題の条件を正確に指定します

coin_aとcoin_bに正の整数の額面を入力し、targetに非負整数の目標値を指定してください。本機能は、最初の硬貨の枚数count_aと2番目の硬貨の枚数count_bがともに非負整数であり、count_aとcoin_aの積にcount_bとcoin_bの積を加えた値が目標値と厳密に一致するかを調べます。表現可能という判定は、近い値や予算以下の組合せを意味するものではありません。等式が完全に成立し、どちらの枚数も負でないことが必要です。目標値0は有効で、両方を0枚にすれば表現できます。額面1も有効であり、その場合はすべての非負目標値を表現できます。3つの入力はいずれも安全な整数でなければなりません。小数、数字の文字列、無限大、JavaScriptで厳密に扱える範囲を超える整数は、暗黙に丸めずエラーとして扱います。また、2つの額面の最大公約数が1、すなわち互いに素であることを計算前に検証します。

合同算術による計算方法を理解します

2つの額面が互いに素であるため、最初の額面には2番目の額面を法とする乗法逆元が存在します。本機能は拡張ユークリッド互除法でその逆元を求め、必要な合同式を満たすcount_aについて、0以上coin_b未満の範囲にある唯一の候補を特定します。その枚数の最初の硬貨が占める値を目標値から引くと余りが得られます。余りが非負ならcoin_bで割り切れ、有効なcount_bが求まるため、両方の枚数を具体的な証明として返します。余りが負なら非負の表現は存在しません。これは推測ではなく完全な判定です。別の整数解では、count_aはcoin_bの整数倍だけ変化し、count_bは反対方向へcoin_aの整数倍だけ変化します。最小の非負候補から始めているため、負の余りを修正しようとするとcount_aが負になります。この方法は多数の枚数を順番に試す総当たりではなく、対数時間で動作します。

結果と入力エラーを正しく読み取ります

representableがtrueの応答にはcount_aとcount_bが含まれます。それぞれを対応する額面と掛けて合計すると、目標値を正確に再現できます。返される組は有効な解の1つです。十分に大きな目標値には複数の表現があり得ますが、本機能は全解の列挙や最適化を目的としていません。falseの場合は適用できる組がないため、枚数の項目を省略します。互いに素でないというエラーとfalseの結果は区別してください。falseは入力が契約を満たしているものの、その目標値を作れないことを示します。エラーは額面の組が本機能の定義域外であり、表現可能性を判定しなかったことを示します。たとえば6と9は共通因子3を持つため、目標値が3で割り切れても拒否されます。この区別により、定義域違反を数学的な不可能性と誤認せずに済みます。計算は決定的でネットワークを使わず、同じ正確な整数入力にはブラウザーでもAPIでも同じ結果を返します。

活用例

正確な支払額を確認します

利用できる2つの額面で必要な合計を作れるか判定し、可能な場合は具体的な枚数の組を取得できます。

整数論の演習を検算します

互いに素な2つの額面に対して目標値を試し、返された解を手計算の結果と比較できます。

固定サイズの組合せを検証します

互いに素な2つの梱包サイズを硬貨に見立て、端数の梱包なしで正確な数量を構成できるか確認できます。

よくある質問

表現可能とは何を意味しますか？

非負整数の枚数について、目標値がcoin_aとcount_aの積にcoin_bとcount_bの積を加えた値と等しいことを意味します。

なぜ額面は互いに素である必要がありますか？

本機能は2額面が互いに素であるという契約に基づき、直接解法で使う合同式の逆元を保証します。1より大きい公約数を持つ組は無効な入力です。

trueの結果には具体的な組合せが含まれますか？

はい。目標値を厳密に再現する非負の組合せとしてcount_aとcount_bを返します。

可能な組合せをすべて返しますか？

いいえ。表現可能性を判定し、存在する場合に解を1つ返します。すべての組の列挙や最適化は行いません。

目標値を0にできますか？

はい。両方の額面を0枚使用することで、0を表現できます。

APIリクエストの料金はいくらですか？

APIリクエスト1回の料金は$0.002です。ブラウザー版では同じ決定的な計算をローカルで実行できます。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/coin-representable-two

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

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/numth/coin-representable-two \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"coin_a":4,"coin_b":7,"target":23}'

const res = await fetch("https://api.kit.forhosting.com/numth/coin-representable-two", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "coin_a": 4,
    "coin_b": 7,
    "target": 23
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/coin-representable-two",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "coin_a": 4,
    "coin_b": 7,
    "target": 23
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/coin-representable-two", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"coin_a":4,"coin_b":7,"target":23}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"coin_a":4,"coin_b":7,"target":23}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/coin-representable-two", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "coin_a": 4,
  "coin_b": 7,
  "target": 23
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.coin_representable_two",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

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

料金

1リクエストあたり$0.002

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

エラー

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

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