python - 2^i-1 形式数字的 GCD

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 和它们自身之外没有其他因子的素数。

i  2^i -1
--------------
1  1 = 1
2  3 = 1,3
3  7 = 1,7
4  15 = 1,3,5,15
5  31 = 1,31
6  63 = 1,3,7,9,21,63
7  127= 1,127
8  255= 1,3,5,15,17,51,85,255

编辑: 只需要为 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 中的低位与 x 中设置的位一样多，也就是说，减法等同于 y &= ~x。减法之后立即将 y 右移其中尾随零的数量，因此您再次获得 2ⁱ-1 形式的数字，但是 popcnt(x) 更短。

从这里可以明显看出，只有长度(即指数)才是重要的，而身份
gcd(2^a-1, 2^b-1) = 2^{gcd(a, b)}-1 从中得出。