問題タブ [number-theory]

http://poj.org/problem?id=1426 (2002 ダッカ地域)を解決しようとしていました。必要な正確なアルゴリズムを思いつくことはできませんでしたが、n が 1 から 200 まで変化したため、2 進数を生成して割り切れるかどうかをチェックすることで、すべての値を事前に計算しました。今、私は一定時間アルゴリズムを持っています:)しかし、これは問題に対する正しいアプローチではないと確信しています。この問題はサイトの基本的な数学の下にあったため、グラフ検索アルゴリズムを使用したくないので、この問題には TLE を与えない数学的な解決策が必要だと思います。

除数に少なくとも数字の 3 が含まれるように、数値の除数の数を見つけるための最も最適化されたアプローチは何ですか?

例: 21=1,3,7,21

したがって、数字の 3 を含む除数は 1 つだけです。

例: 62=1,2,31,62

したがって、数字の 3 を含む除数は 1 つだけで、つまり 31 です。

EDIT-i は、これを行う最善の方法は、数の因数をすべて調べて、数字 3 を含む因数をチェックすることであることに気付きました。

要因を見つける最良の方法：

数の因数を取得する

数値のすべての約数を取得する最良の方法は何ですか?

以下のコード スニペットは、指定された数値が素数であるかどうかを確認します。なぜこれが機能するのか、誰かが私に説明できますか? このコードは、Java 試験のために提供されたスタディ ガイドに記載されていました。

式を満たす最初の n を計算する最速の方法は何ですか?

a^n mod m = 1

ここで、a、n、m は素数または複合 mod です: はモジュラス演算子です

n!modulo p を計算するために次のコードを書きました... n と p が近いと仮定すると...しかし、かなり面白い方法で実行されているため、バグを理解できません..どこかにオーバーフローがあります..制約は1 < P <= 2*10^9

1 <= N <= 2*10^9 ですが、いくつかのケースでは問題なく動作します...エラーの可能性があります。私は使用しました

p素数です....そしてウィルソンの定理(p-1)! mod p = p-1

セットのフロベニウス数は、セットの数の gcd が 1 である場合に存在します。すべての要素の gcd が 1 であるような最大 10 個の要素を持つ正の整数のセットが与えられた場合、セットのフロベニウス数をどのように計算できますか? ?

元の問題へのリンクは次のとおりです: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf シルベスターの公式を使用して、2 つの要素のセットのフロベニウス数を見つけることができます。

別の質問に答えているときに、Symbolic Math Toolboxを使用せずに整数のすべての因数を実際に見つけるにはどうすればよいかという質問に出くわしました。

例えば：

戻り値：

したがって、 「1」が欠落しているすべての素因数を返します。

そして、すべての要素を返す関数を探しています( 1と数値自体は重要ではありませんが、それらはいいでしょう)

の意図した出力x = 60:

おそらくベクトル化できることを除けば、かなりかさばるソリューションを思いつきましたが、エレガントなソリューションはありませんか?

また、perms には 11 未満のベクトル長が必要なため、このソリューションは特定の大きな数では失敗すると思います。