0

如何获得 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
4

3 回答 3

4

考虑二进制 GCD 算法。如果两个操作数都是 2 i -1 的形式，则可以大大简化。

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

在循环中，在减法中，您有两个形式为 2 i -1 的数字，并且左侧大于右侧，因此减法只会重置与y设置的位一样多的低位in x，即减法等价于y &= ~x。减法之后立即右移y其中尾随零的数量，因此您再次获得了 2 i -1 形式的数字，但popcnt(x)更短。

由此可见，只有长度（即指数）很重要，并且恒等式
gcd(2 a -1, 2 b -1) = 2 gcd(a, b) -1 随之而来。

于 2014-02-23T12:06:23.930 回答
1

这些数字非常小。借助 Python 的内置 bignum 处理，它们完全可以fractions.gcd使用欧几里得算法：

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

您的错误来自其他地方。当您尝试遍历 10000 个元素列表中的所有数字对时，您甚至可能只是超时。有近 5000 万对这样的对。根据您获得的时间，您的算法可能太慢了。

于 2014-02-23T11:49:50.003 回答
0

这是一种简单的方法，您可以使用 euclid 的算法来求解 2 的幂，而无需实际评估它们：-

我们需要找到 a%b 来使用 GCD 的 euclids 算法求解：-

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

a>b

我们需要表达 a = 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

因此 m 再次具有相似的两个负 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

于 2014-02-24T12:13:10.447 回答