問題タブ [number-theory]

モジュラス剰余で除算を行うにはどうすればよいですか?

例: 9^2012 を 11 で割った余りを求めます。

剰余演算を使用すると、9 == 1(mod 4) となるため、9^2012 == 1^2012(mod 4) となります。したがって、9^2012 == 1(mod 4) です。また、11 == 3(mod 4) です。質問に答えるために、私は 1(mod 4)/3(mod 4) をしようとしています。これを行う方法はありますか？

私はビー玉 (小さなガラス玉) をいくつか (たとえば n 個) 持っており、それらを保管するためにいくつかの箱を購入するつもりです。ボックスは次の 2 種類です。

使用済みの各ボックスをその容量までいっぱいにして、それらを購入する総コストを最小限に抑えたい. ビー玉を箱にどのように分配するかを理解するのが難しいので、あなたの助けを求めます. あなたのプログラムも効率的にしたいです。

入力ファイルには、複数のテスト ケースが含まれる場合があります。各テスト ケースは、整数 n (1 <= n <= 2,000,000,000) を含む行で始まります。2 行目には c1 と n1 が含まれ、3 行目には c2 と n2 が含まれます。ここで、c1、c2、n1、n2 はすべて 2,000,000,000 より小さい値を持つ正の整数です。

最初の行の n にゼロを含むテスト ケースは、入力を終了します。

入力のテスト ケースごとに、最小コストの解 (2 つの非負の整数 m1 と m2、ここで mi = 必要なタイプ i ボックスの数) を含む行が存在する場合はそれを出力し、そうでない場合は "failed" を出力します。

解決策が存在する場合、それは一意であると想定できます。

以下のコードは完全に機能しますが、その背後にある数学を誰かに説明してもらいたいです。基本的に、それはどのように機能しますか？

以下で説明するタスクが理論的に可能かどうか、可能であればどうすればそれができるかを知りたいです。

要素の空間 (つまり、とNの間のすべての数字)が与えられます。その空間のすべての順列の空間を見て、それを と呼びましょう。の番目のメンバーは、 をマークすることができ、辞書式番号 の順列です。0N-1SiSS[i]i

たとえば、Nが 3 の場合S、順列のリストは次のようになります。

(もちろん、大きな を見るとN、このスペースは非常に大きくなりN!ます。正確には。)

さて、インデックス番号iで順列を取得する方法と、その逆の方法 (特定の順列の辞書式番号を取得する方法) を既に知っています。しかし、もっと良いものが必要です。

一部の順列は、それ自体が巨大になる可能性があります。たとえば、 を見ているとしN=10^20ます。(のサイズはS、(10^20)!スタック オーバーフローの質問でこれまでに言及した最大の数だと思います:)

そのスペースのランダムな順列だけを見ている場合、辞書式番号で各アイテムを計算することは言うまでもなく、ハードドライブにすべてを保存することができないほど大きくなります。私が欲しいのは、その順列でアイテムにアクセスし、各アイテムのインデックスも取得できるようにすることです。つまり、与えられNたi順列を指定するには、インデックス番号を受け取り、そのインデックスにある番号を見つける関数と、番号を受け取り、それがどのインデックスにあるかを見つける別の関数を用意します。でそれを行いたいO(1)ので、順列の各メンバーを保存または反復する必要はありません。

クレイジー、あなたは言いますか？不可能？そうかもしれません。しかし、次のことを考慮してください。AES のようなブロック暗号は、基本的に順列であり、上で概説したタスクをほぼ達成します。AES のブロック サイズは16 バイトNです。( のサイズは重要ではありませんが、驚異的な、または約であり、「スタック オーバーフローで言及された最大数」の最近の記録を上回っています :)256^1610^38S(256^16)!10^85070591730234615865843651857942052838

各 AES 暗号化キーは、 上の 1 つの順列を指定しN=256^16ます。その順列は、太陽系の原子よりも多くのメンバーを持っているため、コンピューターに完全に保存できませんでした. ただし、アイテムへのアクセスは許可されます。AES を使用してデータを暗号化することにより、データをブロックごとに調べ、ブロック ( のメンバーrange(N)) ごとに暗号化されたブロックを出力します。そのメンバーはrange(N)、順列の元のブロックのインデックス番号にあります。復号化するときは、逆のことを行っています (ブロックのインデックス番号を見つける) O(1)。

AES やその他のブロック暗号を使用する際の問題は、非常に具体的NなN.S[i]私が好きな順列。

サイズと順列番号O(1)を指定して、順列でアイテム アクセスを取得することは可能ですか? もしそうなら、どのように？Ni

(幸運にもここでコードの回答を得ることができれば、それらが Python で提供されることを感謝します。)

更新：

一部の人々は、置換数自体が非常に巨大であり、数を読み取るだけではタスクが実行不可能になるという悲しい事実を指摘しました。次に、私の質問を修正したいと思います:順列の辞書式番号の階乗表現へのアクセスが与えられた場合、O(できるだけ小さい)で順列の任意のアイテムを取得することは可能ですか?

問題: http://www.spoj.com/problems/DIVREL

問題は、与えられた要素の集合から、倍数でない (b 形式で割り切れる) 要素の最大数を見つけることだけです。要素からその倍数へのエッジを作成してグラフを作成すると、それは DAG になります。

ここで問題は、ディルワースの定理を使用してアンチチェーンのカーディナリティに等しいすべての頂点を含むチェーンの最小数を見つけることに変わります。これは部分的に順序付けられたセットであるためです。

最小チェーンは二部マッチングを使用して見つけることができます (方法: 最小パス カバーです) が、アンチチェーン要素自体を見つけることができませんか?

一連の画像のサイズを非常に小さく変更して、画像分析を実行できるようにしたいと考えています。ベクトル比較のために、それらすべてに同じ数のピクセルが含まれるようにします。合成度が高いので「120」を選びました。すべての画像を 12x10 にサイズ変更できますが、縦横比が 1.2 でない画像では必要以上に引き伸ばされる可能性があります。

元の縦横比に最も近い新しい幅と高さを選択するにはどうすればよいですか?

参考までに、120 の約数は{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120} なので、有効なサイズは 12x10 になります。 10x12、8x15、15x8、6x20、20x6 など。

編集:正方形の画像と一般的な 16:9 の比率が可能になるため、144 の方が適切な選択であった可能性があります。