math@gcd
最大公約数を求める関数です。
func gcd(a: int, b: int): int | |
| a | 整数1 |
| b | 整数2 |
| 戻り値 | aとbの最大公約数 |
計算量: aとbの小さいほうを
として、
として、aとbのどちらかは0以外でなければなりません。 aやbが負の場合は、絶対値の最大公約数に等しいです。 すなわち、
。
。| 発生条件 | ビルド | 例外コード |
|---|---|---|
| aとbがともに0 | dbgのみ | 0xE9170006 |
math@lcm
最小公倍数を求める関数です。
func lcm(a: int, b: int): int | |
| a | 整数1 |
| b | 整数2 |
| 戻り値 | aとbの最小公倍数 |
計算量: aとbの小さいほうをとして、
として、aとbのどちらかは0以外でなければなりません。 aやbが負の場合は、絶対値の最小公倍数に等しいです。 すなわち、
。
。| 発生条件 | ビルド | 例外コード |
|---|---|---|
| aとbがともに0 | dbgのみ | 0xE9170006 |
math@modMul
オーバーフローさせずに乗算の剰余を求める関数です。
func modMul(a: int, b: int, modulus: int): int | |
| a | 整数1(0以上の値) |
| b | 整数2(0以上の値) |
| modulus | 除算する値(0以上の値) |
| 戻り値 | 「a*b%modulus」の値 |
計算量: aとbの小さいほうをとして、
として、単に「a*b%modulus」を計算すると、大きな値のときにオーバーフローして正確な結果が求まりませんが、この関数はオーバーフローを回避して計算するため正確な値が求まります。
| 発生条件 | ビルド | 例外コード |
|---|---|---|
| a、b、modulusのいずれかが負 | dbgのみ | 0xE9170006 |
math@modPow
オーバーフローさせずに冪の剰余を求める関数です。
func modPow(value: int, exponent: int, modulus: int): int | |
| value | 整数1(0以上の値) |
| exponent | 整数2(0以上の値) |
| modulus | 除算する値(0以上の値) |
| 戻り値 | 「value^exponent%modulus」の値 |
計算量: exponentをとして、
として、単に「value^exponent%modulus」を計算すると、大きな値のときにオーバーフローして正確な結果が求まりませんが、この関数はオーバーフローを回避して計算するため正確な値が求まります。
| 発生条件 | ビルド | 例外コード |
|---|---|---|
| value、exponent、modulusのいずれかが負 | dbgのみ | 0xE9170006 |
math@permutationNext
次の順列を取得する関数です。
func permutationNext(array: []int): bool | |
| array | 順列 |
| 戻り値 | arrayが最初の順列にならなければtrue、なればfalse |
arrayを昇順にソートしておき、この関数を繰り返し呼ぶことで、arrayの要素の並びが次に大きな並びに書き換わり、すべての順列を辞書順に列挙できます。 arrayが再度昇順になったとき、戻り値はfalseになります。
例えばarrayの初期値が[1,3,5]の場合、[1,3,5]、[1,5,3]、[3,1,5]、[3,5,1]、[5,1,3]、[5,3,1]、[1,3,5]と変化します。
math@permutationPrev
前の順列を取得する関数です。
func permutationPrev(array: []int): bool | |
| array | 順列 |
| 戻り値 | arrayが最後の順列にならなければtrue、なればfalse |
arrayを降順にソートしておき、この関数を繰り返し呼ぶことで、arrayの要素の並びが次に小さな並びに書き換わり、すべての順列を辞書順の逆順に列挙できます。 arrayが再度降順になったとき、戻り値はfalseになります。
例えばarrayの初期値が[5,3,1]の場合、[5,3,1]、[5,1,3]、[3,5,1]、[3,1,5]、[1,5,3]、[1,3,5]、[5,3,1]と変化します。
math@prime
素数かどうかを高速に判定する関数です。
func prime(n: int): bool | |
| n | 整数 |
| 戻り値 | nが素数ならtrue、素数でなければfalse |
計算量: nが96000以下のときは、
。 nが96000より大きい場合は、nを、繰り返し回数を
として、
。 繰り返し回数はnがintの範囲だと最大でも12になる
。 nが96000より大きい場合は、nを、繰り返し回数をとして、。 繰り返し回数はnがintの範囲だと最大でも12になるnが1以下の場合は素数ではないためfalseが返ります。
素数バッファと十分に繰り返されるミラー・ラビン素数判定法を併用し、誤りのない素数判定を高速に行います。
math@primeFactors
素因数分解を高速に行う関数です。
func primeFactors(n: int): []int | |
| n | 整数 |
| 戻り値 | nの素因数 |
計算量: 正確な計算量は未解決
戻り値の配列には、nの素因数が昇順に格納されます。 例えばnが18のとき、戻り値は「[2, 3, 3]」になります。
nが1以下の場合、空の配列が返ります。
ポラード・ロー素因数分解法の改良版を十分繰り返し適用し、誤りのない素因数分解を高速に行います。
math@searchBreadthFirst
幅優先探索を行う関数です。
func searchBreadthFirst(itemNum: int, maxDepth: int, callback: func<([]int, kuin@Class): bool>, data: kuin@Class): bool | |
| itemNum | 各要素のパターンの数 |
| maxDepth | 最大の要素数 |
| callback | コールバック関数。第2引数にはdataの値が渡る |
| data | コールバック関数に渡される任意のデータ |
| 戻り値 | 走査が最後まで完了したらtrue、中断したらfalse |
callbackにnullを渡してはいけません。 dataにはnullを渡すことができます。
すべての要素の列に対して幅優先でcallbackが呼ばれます。 例えばitemNumが3、maxDepthが2のとき、[0]、[1]、[2]、[0,0]、[0,1]、[0,2]、[1,0]、[1,1]、[1,2]、[2,0]、[2,1]、[2,2]の順番で要素の列がcallbackの第1引数に渡されます。
callback
戻り値をfalseにすると、それ以降の走査が打ち切られてsearchBreadthFirstを抜けます。
func callback(array: []int, data: kuin@Class): bool | |
| array | 要素の列 |
| data | searchBreadthFirstのdataに渡したデータ |
| 戻り値 | 走査を続行するならtrue、中断するならfalse |
math@searchDepthFirst
深さ優先探索を行う関数です。
func searchDepthFirst(itemNum: int, maxDepth: int, callback: func<([]int, kuin@Class): bool>, data: kuin@Class): bool | |
| itemNum | 各要素のパターンの数 |
| maxDepth | 最大の要素数 |
| callback | コールバック関数。第2引数にはdataの値が渡る |
| data | コールバック関数に渡される任意のデータ |
| 戻り値 | 走査が最後まで完了したらtrue、中断したらfalse |
callbackにnullを渡してはいけません。 dataにはnullを渡すことができます。
すべての要素の列に対して深さ優先でcallbackが呼ばれます。 例えばitemNumが3、maxDepthが2のとき、[0]、[0,0]、[0,1]、[0,2]、[1]、[1,0]、[1,1]、[1,2]、[2]、[2,0]、[2,1]、[2,2]の順番で要素の列がcallbackの第1引数に渡されます。
callback
戻り値をfalseにすると、それ以降の走査が打ち切られてsearchDepthFirstを抜けます。
func callback(array: []int, data: kuin@Class): bool | |
| array | 要素の列 |
| data | searchDepthFirstのdataに渡したデータ |
| 戻り値 | 走査を続行するならtrue、中断するならfalse |
math@searchPermutation
順列の探索を行う関数です。
func searchPermutation(itemNum: int, callback: func<([]int, kuin@Class): bool>, data: kuin@Class): bool | |
| itemNum | 各要素のパターンの数 |
| callback | コールバック関数。第2引数にはdataの値が渡る |
| data | コールバック関数に渡される任意のデータ |
| 戻り値 | 走査が最後まで完了したらtrue、中断したらfalse |
callbackにnullを渡してはいけません。 dataにはnullを渡すことができます。
すべての順列に対して昇順でcallbackが呼ばれます。 例えばitemNumが3のとき、[0,1,2]、[0,2,1]、[1,0,2]、[1,2,0]、[2,0,1]、[2,1,0]の順番で要素の列がcallbackの第1引数に渡されます。
callback
戻り値をfalseにすると、それ以降の走査が打ち切られてsearchPermutationを抜けます。
func callback(array: []int, data: kuin@Class): bool | |
| array | 要素の列 |
| data | searchPermutationのdataに渡したデータ |
| 戻り値 | 走査を続行するならtrue、中断するならfalse |