擅长:python、mysql、java
<p>这里有一个简单的方法,你可以使用欧几里得的算法来求解二次幂,而不需要实际计算它们:</p>
<blockquote>
<p>we need to find a%b to solve using euclids algorithm for GCD :-</p>
<p>a = 2^x-1 b = 2^y-1 </p>
<p>and a>b</p>
<p>we need to express a = k*b + m where m < b then a%b = m</p>
<p>suppose k = 2^(x-y) </p>
<p>2^x - 1 = 2^(x-y)*(2^y-1) + m , m = 2^(x-y)-1</p>
<p>hence </p>
<p>a%b = m = 2^(x-y) -1 </p>
<p>hence m is again in similar power of two minus 1 form hence we can
apply euclids algorithm on it.</p>
</blockquote>
<p><strong>进一步分析:-</strong></p>
<pre><code>a = 2^x-1
b = 2^y-1
GCD(a,b) = F(x,y)
where
F(x,y) = x if x==y
F(x,y) = F(x-y,y) if x > y
F(x,y) = F(x,y-x) if y < x
From further analysis F(x,y) = GCD(x,y)
</code></pre>
<p>参考号:-<a href="http://en.wikipedia.org/wiki/Greatest_common_divisor" rel="nofollow">GCD</a></p>