数字形式为2^i-1的最大公约数

Question

如何获得GCD（2^a[I]-1,2^a[j]-1） 1<；=a[x]<；=100

from fractions import gcd
powj=pow(2,n[j])-1
powk=pow(2,n[k])-1
gcdjk=gcd(powj,powk)

对于大数值会导致问题，并产生运行时错误。
我在2^I-1值中看不到模式，除了除了除了1和它们本身之外没有其他因子的素数。在

^{pr2}$

编辑：只需为表格2^i-1的数字求解此问题。代码如下：

import sys
import math
from fractions import gcd

t=int(input())
for i in range(0,t):
    door=0
    c=int(input())
    n = map(int,sys.stdin.readline().split(' '))
    for j in range(0,c-1):
        for k in range(j+1,c):
            if( gcd(n[j],n[k]) == n[k]):
                powj=pow(2,n[j])-1
                powk=pow(2,n[k])-1
                gcdjk=gcd(powj,powk)
                if(gcdjk==powk):
                    door = door+1
                else:
                    door = door-gcdjk
    print (door)

输入样本：

2
3
10 2 3
2
3 5

限制条件：

1<=T<=20
1<=ArraySize<=10^5
1<=a[i]<=100

Answer 1

这里有一个简单的方法，你可以使用欧几里得的算法来求解二次幂，而不需要实际计算它们：

we need to find a%b to solve using euclids algorithm for GCD :-

a = 2^x-1 b = 2^y-1

and a>b

we need to express a = k*b + m where m < b then a%b = m

suppose k = 2^(x-y)

2^x - 1 = 2^(x-y)*(2^y-1) + m , m = 2^(x-y)-1

hence

a%b = m = 2^(x-y) -1

hence m is again in similar power of two minus 1 form hence we can apply euclids algorithm on it.

进一步分析：-

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)

参考号：-GCD

Answer 2

考虑一下binary GCD algorithm。如果两个操作数的形式都是2ⁱ-1，则可以大大简化。在

首先，在第一步的末尾显然没有零，所以直接进入循环。在

在循环中，在减法中，您有两个形式为2ⁱ-1的数字，并且左手边比右手边大，所以减法只重设y中的低位与{}中设置的位一样多，也就是说，减法相当于y &= ~x。减法之后紧接着将y右移，后面的零个数是2ⁱ-1，但是popcnt(x)要短一些。在

由此看来，只有长度（即指数）才是重要的，恒等式
gcd（2^a-1，2^b-1）=2^{gcd（a，b）}-1紧随其后。在

Answer 3

这些数字很小。使用Python内置的bignum处理，它们完全可以满足fractions.gcd使用的欧几里德算法：

>>> fractions.gcd(2**50-1, 2**100-1)
1125899906842623L

你的错误来自其他地方。当您尝试迭代10000个元素列表中的所有对数字时，您甚至可能只是超时了。大约有5000万对。根据你得到的时间，你的算法可能只是太慢了。在