数字形式为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

考虑一下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紧随其后。在