GCD的形式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和自身以外沒有其他因素的質數。

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 ONLY的號碼。以下是代碼：

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，並且左側比右側大，所以減法只是復位儘可能多的低位在y中，因爲在x中設置了位，所以減法相當於y &= ~x。減法之後立即將y向右移動尾隨零的數量，所以你再次有一個表格編號，但是popcnt(x)縮短了。

從這一點應該是顯而易見的，只有長度（即指數）以往關係，和標識
GCD（2 ^一個 -1,2- ^b -1）= 2 ^{GCD（A，B ）} -1跟着它。

Answer 2

這些數字是非常小的。與Python的內置BIGNUM處理，他們受過良好的歐幾里德算法fractions.gcd使用的範圍內：

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

你的錯誤是從別的地方來了。當您嘗試迭代10000個元素列表中的所有數字對時，您甚至可能會超時。有近5000萬個這樣的對。根據您獲得多少時間，您的算法可能會太慢。

Answer 3

下面是簡單的方法ü可以使用歐幾里德的算法來解決的兩個大國，而無需實際評價他們： -

，我們需要找到一個％b。使用euclids算法GCD解決： -

A = 2^X-1 b = 2^Y-1

和a> b的

我們需要表達一個= K * b + m，其中m < b，則A％b = M

假設K = 2 ^（XY）

2^X - 1 = 2 ^（XY）*（2^Y-1）+ M，M = 2 ^（XY）-1

因此

A％b = M = 2 ^（XY）-1

因此米再次處於兩個零下1形式類似的電源，因此，我們可以 它適用euclids算法。

進一步分析： -

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