私のプロジェクトでは、問題の一部があります。しかし、簡単にするために、ここで問題が定式化されています。2 つの正の互いに素な整数があります:aとb、ここでa < b. a1 ～の倍数b-1がリストされ、その後に による剰余演算が続きbます。
a mod b, 2*a mod b, 3*a mod b, ... ,(b-1)*a mod b
さて、別の整数がありますn ( 1 <= n < b)。リストの最初の数字を通して、たとえば( )nよりも小さい数字がいくつあるかを見つける必要があります。これはブルート フォース アプローチで実行できるため、 .m1 <= m < bO(n)
例：
a=6, b=13, n=8, m=6
リストは次のとおりです。
6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7
これは、1 から 12 までの数値の順列です。これは、別の数値、つまり を含めると、任意の 2 つの互いに素なモジュラス演算によって数値の順列が生成されるため0です。を取るa= 2, b=13と、リストは になり2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11、パターンが得られます。aとが非常に大きい場合b(私のプロジェクトでは最大 10^20 になる可能性があります)、そのような大きな数のパターンを推測する方法がわかりません。
例に戻るとn = 8、リストから最初の数字を取得します。
6, 12, 5, 11, 4, 10, 3, 9
less-than演算子をで適用すると、以下のリストで説明するように、3m = 6未満の合計数が得られます。m
0, 0, 1, 0, 1, 0, 1, 0
ここで、0 は 未満ではないことを示しm、1 は未満であることを示しmます。
上記のアルゴリズムは でありO(n)、 の範囲では受け入れられない[0, 10^20]ため、コミュニティはヒント/手がかり/ヒントを提供して、O(log n )解決策、またはより良いO(1)解決策に到達できるようにすることができますか?