-5

(2^n)%p (n は 10^36 の次数の非常に大きな数で、p は素数) を見つけるように求める質問に行き詰まりました。このアルゴリズム全体で使用できますが、10^36 が非常に大きいため、スタック オーバーフローが発生します。

double power(double a,double b,int mod)
{
if (b==0)
return 1;
else if(b%2==0)
return square(power(a,b/2,mod))%mod;
else return power(a,b-1,mod)%mod;
}

彼らの他の方法やこれに対する改善はありますか??

4

2 に答える 2

1

分割統治法を使用できます。

基本的な考え方は次のとおりです。

2^8 = (2^4)^2 2^4 = (2^2)^2

したがって、2^2 を 1 回計算し、それを 2 乗して 2^4 を得る必要があります。次に、その結​​果を 2 乗して 2^8 などを取得します。

示されているケースは、n が 2 の累乗の場合に完全に機能します。ただし、このような累乗を 2 または 3 のサブ問題に分割することは可能です。

たとえば、n = 20 の場合、(2^10)^2 になります。n = 21 の場合、(2^10)^2 * 2 になります。

したがって、電力の奇数と偶数の値に応じて、コンポーネントに分解できます。

イラストが明確だったことを願っています。

于 2012-01-05T10:50:43.760 に答える
-1

この場合、Pythonが役に立ちます。Python では、データ型の範囲を気にする必要はありません。データの値を指定するだけで、Python は変数のデータ型を自動的に調整します。

于 2012-01-05T10:50:37.037 に答える