「繰り返し二乗法」の編集履歴（バックアップ）一覧はこちら

「繰り返し二乗法」(2013/11/02 (土) 03:10:04) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

繰り返し二乗法のアルゴリズムを答えよ。
====
0を含むすべて自然数は2のべき乗の和の組み合わせで表すことが出来る。2進数がその例である。
nを2のべき乗の和で表すと
>||
n = 2^(k_1) + 2^(k_2) + 2^(k_3) + ...
||<
よって、
>||
x^n = x^(2^k_1) x^(2^k_2) x^(2^k_3) ...
||<
2進数で操作をすればよいので1のビットが立つ部分iについて、resにx^iを掛けていく。
下位ビットから考えているのでxは順次二乗していけばよい。nの1と0のビットの数だけ処理するのみなのでO(log n)でxのべき乗を高速に求められる。

>||
typedef long long ll;

ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while(n > 0) {
    if(n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
||<

*繰り返し二乗法
**解説
0を含むすべて自然数は2のべき乗の和の組み合わせで表すことが出来る。2進数がその例である。
nを2のべき乗の和で表すと
>||
n = 2^(k_1) + 2^(k_2) + 2^(k_3) + ...
||<
よって、
>||
x^n = x^(2^k_1) x^(2^k_2) x^(2^k_3) ...
||<
2進数で操作をすればよいので1のビットが立つ部分iについて、resにx^iを掛けていく。
下位ビットから考えているのでxは順次二乗していけばよい。nの1と0のビットの数だけ処理するのみなのでO(log n)でxのべき乗を高速に求められる。

>||
typedef long long ll;

ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while(n > 0) {
    if(n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
||<