0

1<=a[x]<=100 で GCD(2^a[i]-1,2^a[j]-1) を取得するにはどうすればよいですか

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

数が多いと問題が発生し、実行時エラーが発生します。
素数が 1 とそれ自体以外に因数を持たない場合を除いて、2^i-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

1

これらの数字はかなり小さいです。Python のビルトイン bignum 処理により、ユークリッド アルゴリズムのfractions.gcd使用の範囲内に収まります。

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

あなたのエラーは別の場所から来ています。10000 要素のリスト内の数値のすべてのペアを反復しようとすると、タイムアウトすることさえあるかもしれません。そのようなペアは約5000万あります。取得する時間によっては、アルゴリズムが遅すぎる可能性があります。

于 2014-02-23T11:49:50.003 に答える