0

この問題を解決しようとしています:

正の数 n の場合、S(n) を整数 x の合計として定義し1 < x < nますx^3 ≡ 1 mod n。

の場合n=91、x には 8 つの可能な値、つまり 9、16、22、29、53、74、79、81 がありS(91)=9+16+22+29+53+74+79+81=363ます。

S(13082761331670030) を見つけます。

もちろん、私のコードは機能しS(91)、検索しようとするとS(13082761331670030)2 つの異なるエラーが発生します。

これが私のコードです：

 def modcube(n):
     results = []
     for k in range(1,n):
            if k**3%n==1:
             results.append(k)
     return results

これによりOverflow error: range has too many items.、「range」の代わりに「xrange」を使用しようとすると、python int too large to convert to c long というエラーが表示されます。また、成功せずに他のいくつかのことを試しました。

正確な解決方法を教えずに、誰かが私を正しい方向に向けることができますか?
ネタバレはご遠慮ください。Python は初めてなので、次のオプションは Java でこれを実装してみることです。

4

2 に答える 2

2

ここで 2 つの概念を理解する必要があると思います。

1. C および Python での整数表現

使用する Python の実装は、C 言語を使用して記述されているため、CPython と呼ばれます。C では、長整数 (通常) は 32 ビット長です。これは、-2147483647 から 2147483648 の間の整数で動作できることを意味します。Python では、整数がこの範囲を超えると、整数のサイズがコンピューターのメモリによってのみ制限される任意精度の整数に変換されます。ただし、これらの任意の整数 (Python では長整数と呼ばれます) の操作は、32 ビット整数の操作よりも桁違いに遅くなります。

range2.との違いxrange:

rangeリストを生成します。がある場合はrange(10)、リスト[0, 1, ... 9]全体をメモリに保存します。これが、13082761331670030 個の項目のリストをメモリに格納するのが面倒な理由です。各数値が 64 ビットであると仮定すると、リスト全体を格納するには 93 TB の RAM が必要になります!

xrangeイテレータを生成します。各数値を 1 つずつ返します。このようにして、リスト全体をメモリに保存する必要なく、リストの各番号に対して操作を実行できます。しかし、繰り返しになりますが、13082761331670030 の異なる数値で計算を実行すると、思ったよりも時間がかかる可能性があります... もう 1 つのことxrangeは、Python の長整数では機能しないことです。(速度上の理由から) 32 ビット整数に制限されています。これが、あなたのプログラムが を使用して動作しない理由xrangeです。

結論: Project Euler の問題は (多かれ少なかれ) 難易度によって分類されます。最初は下位の問題から始めるべきです。

于 2013-03-21T04:25:06.390 に答える
1

解決策ではなく、ヒントが必要でした。

ヒント：

  1. 13082761331670030 の素因数は次の素数に等しいと考えてください: 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43

  2. 中国剰余定理

  3. この条件を満たすx^3 ≡ 1 mod n値が 3 以外にないというわけではありません。具体的には、prime1 ** (prime2 - 2) % prime2

私のPythonソリューションは86ミリ秒です...

于 2013-03-21T05:51:07.903 に答える